1082.cpp

来自「自己的ac代码 在acm.zju.edu.cn 上的题目」· C++ 代码 · 共 57 行

#include<stdio.h>
int main()
{
	int i,j,k,l;
	int a[105][105];
	int n;
	int t1,t2;
	int maxn,minn;
	int disjoint;
	int p;
	while(scanf("%d",&n))
	{
		if(n==0)break;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(i!=j)a[i][j]=1000000;
				else a[i][j]=0;

		for(i=1;i<=n;i++)
		{
			scanf("%d",&l);
			for(j=1;j<=l;j++)
			{
				scanf("%d%d",&t1,&t2);
				a[i][t1]=t2;
			}
		}
		for(k=1;k<=n;k++)
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
					if(a[i][k]+a[k][j]<a[i][j])a[i][j]=a[i][k]+a[k][j];
		int minn=1000000;
		disjoint=0;
		for(i=1;i<=n;i++)
		{
			int maxn=0;
			for(j=1;j<=n;j++)
			{
				if(a[i][j]>maxn)maxn=a[i][j];
			}
			
			if(maxn<minn){minn=maxn;p=i;}
		}
		if(minn>=1000000)disjoint=1;
		if(disjoint==1)
			printf("disjoint\n");
		else
			printf("%d %d\n",p,minn);
	}
	return 0;
}