1002 stockbroker grapevine.cpp

吉林大学困扰多人的1002题

//2007.5.8
#include<cstdio>
int main()
{
	int n,m,r,i,j,k,time;
	while(scanf("%d",&n),n>0)
	{
		int t[101][101]={0};
		for(i=1;i<=n;i++)
		{
			scanf("%d",&m);
			for(j=1;j<=m;j++)
			{
				scanf("%d",&r);
				scanf("%d",&t[i][r]);
			}
		}
		for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(i!=j&&t[j][i])
			{
				for(k=1;k<=n;k++)
				{		
					if(t[i][k]&&k!=i&&k!=j)
					{
						time=t[j][i]+t[i][k];
						if(time<t[j][k]||t[j][k]==0)t[j][k]=time;
					}
				}
			}
		}
		int sum=10000,w;
		for(i=1;i<=n;i++)
		{
			for(j=1,time=0;j<=n;j++)
			{
				if(i!=j)
				{
					if(t[i][j]==0)
					{
						time=0;break;
					}
					else if(time<t[i][j])time=t[i][j]; 
				}
			}		
			if(sum>time&&time>0)
			{
				sum=time;w=i;
			}
		}
		if(sum==10000)printf("disjoint\n");
		else printf("%d %d\n",w,sum);
	}
	return 0;
}