#include<stdio.h>
int main()
{
int n,i,k,j,L,M,N,x,t,min;
int map[100][100],flag[100];
memset(map,-1,sizeof(map));
scanf("%d",&n);
for(i=0;i<n;i++)
{
map[i][i]=0;
scanf("%d",&k);
for(j=0;j<k;j++)
{
scanf("%d %d",&x,&t);
map[i][x-1] = t;
}
}
for(L=0;L<n;L++)
for(M=0;M<n;M++)
for(N=0;N<n;N++)
{
if(!(map[M][L]==-1 || map[L][N]==-1))

if(map[M][N]== -1)
map[M][N]=map[M][L]+map[L][N];
if(map[M][N]>map[M][L]+map[L][N])
map[M][N]=map[M][L]+map[L][N];

}
for(M=0;M<n;M++)
flag[M]=1;
for(M=0;M<n;M++)
for(N=0;N<n;N++)
if(map[M][N]==-1)
flag[M]=0
k=0;
for(i=0;i<n;i++)
k=k+flag[i];
if(k==0)
{
printf("deijoint");
system("pause");
return 0;
}

min = 99999;
for(M=0;M<n;M++)
{
k=0;
for(N=0;N<n;N++)
if(k < map[M][N])
k = map[M][N];
if(min > k)
{
min = k;
x = M;
}
}
printf("%d %d",x+1,min);
system("pause");
return 0;
};

 

最后修改日期:2017年10月22日

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。