//每對(duì)頂點(diǎn)之間的最短路徑算法floyd，其實(shí)是動(dòng)歸，O(n
3)，還要注意disjoint
#include<iostream>
using namespace std;
#define M 100
#define INF 20000000
int sb[M+1][M+1];
int d[M+1][M+1];
int n;
int i,j,k;
void Init()
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
sb[i][j]=(i==j?0:INF);
}
void floyd()
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=sb[i][j];
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(d[i][k]+d[k][j]<d[i][j])
d[i][j]=d[i][k]+d[k][j];
}
int main()
{
int mi,v,w,ri,min,max;
while( scanf("%d",&n)==1 && n!=0)
{
Init();
for(i=1;i<=n;i++)
{
scanf("%d",&mi);
for(j=1;j<=mi;j++) { scanf("%d%d",&v,&w); sb[i][v]=w; }
}
floyd();
min=INF;
ri=-1;
for(i=1;i<=n;i++)
{
max=0;
for(j=1;j<=n;j++)
if(d[i][j]>max) max=d[i][j];
if(max<min) { min=max;ri=i;}
}
if(ri==-1) printf("disjoint\n");
else printf("%d %d\n",ri,min);
}
return 0;
}posted on 2009-05-24 16:17
wyiu 閱讀(201)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
POJ