ABC289E广搜求最少步数条件更多

#include <stdio.h>
#define N 2005
int t, n, m, i, j, k, l, a, b, x, y;
int c[N], h[N], f[N][N], q[N*N];
struct AB{
    int a, b, n;
} d[N*2];
void cun(int a, int b){
    d[++k].a = a, d[k].b = b;
    d[k].n = h[a], h[a] = k;
}//不会邻接表，也可以用二维数组存储
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        for(i=1; i<=n; i++){
            scanf("%d", &c[i]);
            for(j=1; j<=n; j++) f[i][j] = 0;
        }//注意赋初值，数组比较大不要memset
        for(i=k=0; i<=n; i++) h[i] = 0;
        for(i=1; i<=m; i++){
            scanf("%d%d", &a, &b);
            cun(a, b);
            cun(b, a);
        }
        f[1][n] = 1, q[1] = 1*N + n;
        for(i=j=1; i<=j; i++){
            a = q[i]/N, b = q[i]%N;//当前状态
            for(k=h[a]; k; k=d[k].n){
                for(l=h[b]; l; l=d[l].n){
                    x = d[k].b, y = d[l].b;//后继状态
                    if(c[x]==c[y] || f[x][y]) continue;
                    f[x][y] = f[a][b] + 1;//记录最小步数
                    q[++j] = x*N + y;
                }
            }
        }
        printf("%d\n", f[n][1]-1);
    }
    return 0;
}