#include <iostream>
#include <limits>
int data[101][101];
int n;
int main()
{
while( scanf("%d",&n), n!= 0 )
{
memset( data, 0, sizeof(data) );
for ( int i= 1; i<= n; ++i )
{
int m;
scanf("%d",&m);
for ( int j= 0; j< m; ++j )
{
int x, y;
scanf("%d%d",&x,&y );
data[i][x]= y;
}
}
for ( int k= 1; k<= n; ++k )
{
for ( int i= 1; i<= n; ++i )
for ( int j= 1; j<= n; ++j )
if ( data[i][k]> 0 && data[k][j]> 0 && (data[i][k]+ data[k][j]< data[i][j] || data[i][j]== 0 ) )
data[i][j]= data[i][k]+ data[k][j];
}
int min= INT_MAX;
int k= 1;
for ( int i= 1; i<= n; ++i )
{
int m= INT_MIN;
bool isok= true;
for ( int j= 1; j<= n; ++j )
{
if ( i!= j && data[i][j]== 0 )
{
isok= false;
break;
}
if ( i!= j && data[i][j]> m ) m= data[i][j];
}
if ( m< min && isok )
{
min= m;
k= i;
}
}
if ( min!= INT_MAX ) printf("%d %d\n", k, min );
else printf("disjoint\n");
}
return 0;
}
posted on 2008-10-02 20:59
Darren 閱讀(172)
評論(0) 編輯 收藏 引用