UVa 567 Risk [Shortest Path]

567    Risk    poao899    Accepted    C++    0.084    2009-12-11 15:33:06                          .

昨天看題目看了十幾分鐘竟然是無腦題=口=


20個點沒有權重的最短路orz

//********************************

#include<stdio.h>
#define INF 1000000
int dist[30][30],cnt,a,b,n;
main(){
    for(int z=1;~scanf("%d",&cnt);z++){
        printf("Test Set #%d\n",z);
        for(int i=0;i<30;i++)
            for(int j=0;j<30;j++)
                dist[i][j]=i==j?0:INF;
        for(int i=1;i<20;i++){
            while(cnt-->0){
                scanf("%d",&n);
                dist[i][n]=dist[n][i]=1;
            }
            scanf("%d",&cnt);
        }
        //Floyd –Warshall
        for(int k=1;k<=20;k++)
            for(int i=1;i<=20;i++)
                for(int j=1;j<=20;j++)
                    if(dist[i][k]+dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k]+dist[k][j];
        for(int i=0;i<cnt;i++){
            scanf("%d%d",&a,&b);
            printf("%2d to %2d:%2d\n",a,b,dist[a][b]);
        }
        puts("");
    }
}