2815720_ac_0ms_80k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 82 行

#include <stdio.h>
#define INF 2100000000

int map[101][101];
int n;

void floyd()
{
	int i, j, k;
 
	for(k = 0; k < n; k++)
	{
		for(i = 0; i < n; i++)
		{
			if(map[i][k]!=INF)
			{
				for(j = 0; j < n; j++)
					if(map[i][k]+map[k][j]<map[i][j])
						map[i][j]=map[i][k]+map[k][j]; 
			}
		}  
	}
}

int main()
{
	int t, num;
	int i, j;
	int a, b;
	int ans, tt, tmp;

	while(scanf("%d",&n)==1,n)
	{
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				map[i][j] = INF;
		for(i = 0; i < n; i++)
		{
			scanf("%d",&t);
			for(j = 0; j < t; j++)
			{
				scanf("%d%d",&a,&b);
				map[i][a-1] = b;
			}
		}
		floyd();
		num = 0;
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
			{
				if(map[i][j]==INF&&i!=j)
				{
					num++;
					break;
				}
			}
		}
		if(num==n)
		{
			puts("disjoint");
			continue;
		}
		ans = INF;
		for(i = 0; i < n; i++)
		{
			tmp = -1;
			for(j = 0; j < n; j++)
			{
				if(i!=j&&map[i][j]>tmp)
					tmp = map[i][j];
			}
			if(tmp < ans)
			{
				ans = tmp;
				tt = i;
			}
		}
		printf("%d %d\n",tt+1,ans);
	}
	return 0;
}