ABC291F稀疏矩阵双向最短路交汇合并

#include <bits/stdc++.h>
#define N 100050
using namespace std;
int n, m, i, j, k, a, b, c, ans, t[N][15], x[N], y[N];
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        for(c=j=1; j<=m; j++){
            scanf("%1d", &k);
            if(!k) continue;
            t[i][c++] = i+j;
        }//每个点至多10条边
    }
    memset(x, 9, sizeof(x));
    x[1] = 0;
    for(i=1; i<n; i++){
        for(j=1; k=t[i][j]; j++){
            x[k] = min(x[k], x[i]+1);
        }//前面往后退，前面已定，后面求最优值
    }//1为起点的单源最短路
    memset(y, 9, sizeof(y));
    y[n] = 0;
    for(i=n-1; i>=1; i--){
        for(j=1; k=t[i][j]; j++){
            y[i] = min(y[i], y[k]+1);
        }//后面往前推，后面已定，前面求最优值
    }//n为起点的单源最短路
    for(k=2; k<n; k++){//枚举不经过k
        ans = 1e9;//两边连接，只能靠k附近的m个点
        for(a=k-1; a>=1&&a>k-m; a--){
            for(i=1; b=t[a][i]; i++){
                if(b <= k) continue;
                ans = min(ans, x[a]+y[b]+1);
            }//a为左边点，b为右边点
        }
        if(ans > N) ans = -1;
        printf("%d ", ans);
    }
    return 0;
}