/*
一张有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");
}
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3898362.html，如需转载请自行联系原作者
