Uva多源の最短問題
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=116&page=show_problem&problem=508
20点を与え、これらの点をつなぐ辺を何度も与え、始点から終点までの最小辺数を求めます。
テーマ分析:この問題は図を所有権の値がすべて1であると見なしてもいいです。すなわち、任意の頂点の間の最も短絡的な問題を求めて、Floydアルゴリズムを使います。
この問題のデータ量が少ないので、直接bfsを使ってもいいです。
コード:
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;
}