题意：

这题真难读懂，简单来说就是n个经理人，每个经理人认识其他的一些经理人，要交流情报，每个经理人只能与认识的人交流，并且交流需要时间，要求从那个经理人开始传情报能使最慢收到情报的经理人耗时最短，输出最短时间

要点：

就是一个Floyd的模板问题，就是题目难懂了一点。

15368826

Accepted

208K

0MS

900B

2016-04-08 19:11:17

#include
    
     #include
     
      #include
      
       #define INF 0x3f3f3fint map[105][105];int n;void floyd(){	for (int k = 1; k <= n; k++)		for (int i = 1; i <= n; i++)			for (int j = 1; j <= n; j++)				if (map[i][j] > map[i][k] + map[k][j])					map[i][j] = map[i][k] + map[k][j];}int main(){	int m,mate,dis;	while (~scanf("%d", &n), n)	{		memset(map, INF, sizeof(map));		for (int i = 1; i <= n; i++)		{			map[i][i] = 0;			//养成良好习惯，指向自己的赋值为0，否则后面可能会出错			scanf("%d", &m);			while (m--)			{				scanf("%d%d", &mate, &dis);				map[i][mate] = dis;			}		}		floyd();		int max,min=INF,ans;		for (int i = 1; i <= n; i++)		{			max = -1;			for (int j = 1; j <= n; j++)			{				if (max < map[i][j])//找出当前i经理人的最短路的最大值					max = map[i][j];			}			if (min > max)			//取最大值中的最小值并保存当前经理人			{				min = max;				ans = i;			}		}		if (min < INF)			printf("%d %d\n", ans, min);		else			printf("disjoint\n");	}	return 0;}