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;}