Uva多源の最短問題


http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&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
",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
",u,v,d[u-1][v-1]); } printf("
"); } return 0; }