uva 567 Risk

点击打开链接uva 567

1思路：最短路+floyd
2分析：题目给定的点的个数为20，那么根据f'loyd的时间复杂度不会超时，那么直接利用floyd即可。
3注意输出的格式问题

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 25
#define INF 0xFFFFFFF

int n , cnt;
long long dis[MAXN][MAXN];

/*初始化dis数组*/
void init(){
    for(int i = 1 ; i <= 20 ; i++){
       for(int j = 1 ; j <= 20 ; j++){
          if(i == j)
            dis[i][j] = 0;
          else
            dis[i][j] = INF;
       }
    }
}

/*求最小值函数*/
long long  min(long long a , long long b){
   return a < b ? a : b;
}

/*floyd算法*/
void floyd(){
     int a , b;
     for(int k = 1;  k <= 20 ; k++){
        for(int i = 1 ; i <= 20 ; i++){
           for(int j = 1 ; j <= 20 ; j++)
              dis[i][j] = min(dis[i][j] , dis[i][k]+dis[k][j]);
        }
     }
     scanf("%d" , &n);
     printf("Test Set #%d\n" , cnt++);
     for(int i = 1 ; i <= n ; i++){
        scanf("%d%d" , &a , &b);
        printf("%2d to %2d: %lld\n" , a , b , dis[a][b]);/*输出问题*/
     }
     printf("\n");
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    int x , a;
    cnt = 1;
    while(scanf("%d" , &x) != EOF){
         init();
         for(int i = 1 ; i <= x ; i++){
            scanf("%d" , &a);
            dis[1][a] = dis[a][1] = 1;
         }
         for(int i = 2 ; i <= 19 ; i++){
            scanf("%d" , &x);
            for(int j = 1 ; j <= x ; j++){
               scanf("%d" , &a);
               dis[i][a] = dis[a][i] = 1;
            }
         }
         floyd();
    }
    return 0;
}