uva oj 567 - Risk(Floyd算法)

/*
一张有20个顶点的图上。
依次输入每个点与哪些点直接相连。
并且多次询问两点间，最短需要经过几条路才能从一点到达另一点。

bfs 水过
*/
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;

struct node{
   int x, step;
   node(){

   }
   node(int x, int step){
      this->x=x;
      this->step=step;
   }
}; 

vector<int>v[25];
queue<node>q;
int vis[25];

int b, e;

void bfs(){
   while(!q.empty())  q.pop();
   node cur;
   q.push(node(b, 0));
   while(!q.empty()){
       cur=q.front();
       q.pop();
       if(cur.x==e){
           printf("%2d to %2d: %d\n", b, e, cur.step);
           return;
       }
       int len=v[cur.x].size();
       for(int i=0; i<len; ++i){
             if(v[cur.x][i]==e){
             printf("%2d to %2d: %d\n", b, e, cur.step+1);
             return;
          }
          if(!vis[v[cur.x][i]]){
               vis[v[cur.x][i]]=1;
             q.push(node(v[cur.x][i], cur.step+1));
          }
       }
   }
}

int main(){
    int n, u;
    int cnt=0;
    while(scanf("%d", &n)!=EOF){
        while(n--){
           scanf("%d", &u);
           v[1].push_back(u);
           v[u].push_back(1);
        }
        for(int i=2; i<=19; ++i){
           scanf("%d", &n);
           while(n--){
              scanf("%d", &u);
              v[i].push_back(u);
              v[u].push_back(i);
           }
        }
        scanf("%d", &n);
        printf("Test Set #%d\n", ++cnt);
        while(n--){
           scanf("%d%d", &b, &e) ;
           bfs();
           memset(vis, 0, sizeof(vis));
        }
        printf("\n");
        for(int i=1; i<=20; ++i)
           v[i].clear();

    }
    return 0;
}
/*
   Floyd 才是正解！
*/
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;

int map[25][25];

void Folyd(){
   for(int k=1; k<=20; ++k)
      for(int i=1; i<=20; ++i)
         for(int j=1; j<=20; ++j)
            if(map[i][j] > map[i][k] + map[k][j])
               map[i][j] = map[i][k] + map[k][j];
}

int main(){
    int n, u, b, e;
    int cnt=0;
    while(scanf("%d", &n)!=EOF){
        memset(map, 0x3f, sizeof(map));
        while(n--){
           scanf("%d", &u);
           map[1][u]=map[u][1]=1;
        }
        for(int i=2; i<=19; ++i){
           scanf("%d", &n);
           while(n--){
              scanf("%d", &u);
              map[u][i]=map[i][u]=1;
           }
        }
        scanf("%d", &n);
        printf("Test Set #%d\n", ++cnt);
        Folyd();
        while(n--){
           scanf("%d%d", &b, &e) ;
           printf("%2d to %2d: %d\n", b, e, map[b][e]);
        }
        printf("\n");
    }
}