Uva 多源最短路问题
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=508
题目大意：给定20个点，以及一些连接这些点的边，然后多次任意给定两点，求起始点到终点所经过的最少边数。
题目分析：此题可以把图看作是一个所有权值均为1的带权无向图，即求任意顶点之间的最短路问题，用Floyd算法。
由于此题的数据量很少，所以直接用bfs也可。
代码：
//权值均为1的多源最短路问题//可以用bfs,由于需要多次查询，故效率不高//可以用floyd算法，O(n^3),查询为O(1)#include #include #include #define INF 100000using namespace std;const int maxn=50;int adj[maxn][maxn];//邻接矩阵int d[maxn][maxn];//记录距离int main(){ int k,u,v; int c=0; while(cin>>k) { c++; printf("Test Set #%d\n",c); memset(adj,0,sizeof(adj)); int i=0; while(k--) { cin>>u; u--; adj[u][i]=1; adj[i][u]=1; } int j; for(j=1;j>k; while(k--) { cin>>u; u--; adj[u][i]=1; adj[i][u]=1; } } for(i=0;i>n; for(i=1;i>u>>v; printf("%2d to %2d:%2d\n",u,v,d[u-1][v-1]); } printf("\n"); } return 0;}