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 ", 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 ", 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 ", ++cnt); 78 while(n--){ 79 scanf("%d%d", &b, &e) ; 80 bfs(); 81 memset(vis, 0, sizeof(vis)); 82 } 83 printf(" "); 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 0x3f3f3f3f 10 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 ", ++cnt); 41 Folyd(); 42 while(n--){ 43 scanf("%d%d", &b, &e) ; 44 printf("%2d to %2d: %d ", b, e, map[b][e]); 45 } 46 printf(" "); 47 } 48 }