1 /* 2 一张有20个顶点的图上。 3 依次输入每个点与哪些点直接相连。 4 并且多次询问两点间，最短需要经过几条路才能从一点到达另一点。 5  6 bfs 水过 7 */ 8 #include<iostream> 9 #include<cstring>10 #include<vector>11 #include<cstdio>12 #include<queue>13 using namespace std;14 15 struct node{16    int x, step;17    node(){18    19    }20    node(int x, int step){21       this->x=x;22       this->step=step;23    }24 }; 25 26 27 vector<int>v[25]; 28 queue<node>q;29 int vis[25];30 31 32 int b, e;33 34 void bfs(){35    while(!q.empty())  q.pop();36    node cur;37    q.push(node(b, 0));38    while(!q.empty()){39        cur=q.front();40        q.pop();41        if(cur.x==e){42            printf("%2d to %2d: %d\n", b, e, cur.step);43            return;44        }45        int len=v[cur.x].size();46        for(int i=0; i<len; ++i){47              if(v[cur.x][i]==e){48              printf("%2d to %2d: %d\n", b, e, cur.step+1);49              return;50           }51           if(!vis[v[cur.x][i]]){52                vis[v[cur.x][i]]=1;53              q.push(node(v[cur.x][i], cur.step+1));54           } 55        }56    }57 }58 59 int main(){60     int n, u;61     int cnt=0;62     while(scanf("%d", &n)!=EOF){63         while(n--){64            scanf("%d", &u);65            v[1].push_back(u);66            v[u].push_back(1);67         }68         for(int i=2; i<=19; ++i){69            scanf("%d", &n);70            while(n--){71               scanf("%d", &u);72               v[i].push_back(u);73               v[u].push_back(i);74            }75         }76         scanf("%d", &n);77         printf("Test Set #%d\n", ++cnt);78         while(n--){79            scanf("%d%d", &b, &e) ;80            bfs();81            memset(vis, 0, sizeof(vis));82         }83         printf("\n");84         for(int i=1; i<=20; ++i)85            v[i].clear();86            87     } 88     return 0;89 }

 1 /* 2    Floyd 才是正解！ 3 */ 4 #include<iostream> 5 #include<cstring> 6 #include<vector> 7 #include<cstdio> 8 #include<queue> 9 #define INF 0x3f3f3f3f10 using namespace std;11 12 int map[25][25];13 14 void Folyd(){15    for(int k=1; k<=20; ++k)16       for(int i=1; i<=20; ++i)17          for(int j=1; j<=20; ++j)18             if(map[i][j] > map[i][k] + map[k][j])19                map[i][j] = map[i][k] + map[k][j];20 }21 22 23 int main(){24     int n, u, b, e;25     int cnt=0;26     while(scanf("%d", &n)!=EOF){27         memset(map, 0x3f, sizeof(map));28         while(n--){29            scanf("%d", &u);30            map[1][u]=map[u][1]=1;31         }32         for(int i=2; i<=19; ++i){33            scanf("%d", &n);34            while(n--){35               scanf("%d", &u);36               map[u][i]=map[i][u]=1;37            }38         }39         scanf("%d", &n);40         printf("Test Set #%d\n", ++cnt);41         Folyd();42         while(n--){43            scanf("%d%d", &b, &e) ;44            printf("%2d to %2d: %d\n", b, e, map[b][e]);45         }46         printf("\n");47     }48 }