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