#include <iostream>

using namespace std;

const int MAXN=100,INF=1<<30-1;
int map[MAXN][MAXN];

inline void eqmin(int & a,int b)
{
	if (b<a) a=b;
}

int main()
{
	int n,m,a,b;
	for(cin>>n;n!=0;cin>>n)
	{
		for(int i=0;i<n;i++)
		    for(int j=0;j<n;j++) map[i][j]=INF;
		for(int i=0;i<n;i++)
		{
			cin>>m;
			for(int j=0;j<m;j++)	
			{
				cin>>a>>b;
				map[i][a-1]=b;
			}
		}
		
		for(int k=0;k<n;k++)
			for(int i=0;i<n;i++)
		  	  for(int j=0;j<n;j++) 
		  	  if (i!=j) eqmin(map[i][j],map[i][k]+map[k][j]);
		
		int tmax=INF,res;
		for(int i=0;i<n;i++)
		{
			int maxn=0;
			for (int j=0;j<n;j++) if (i!=j && map[i][j]>maxn) maxn=map[i][j];
			if (maxn<tmax) tmax=maxn,res=i;
		}
		cout<<res+1<<' '<<tmax<<endl;
	}
	return 0;
}

• Re:水题啊！Floyd0MS秒杀 (871) suweixuan 2012-04-22 16:32:53