POJ1125 Stockbroker Grapevine(最短路径)

题意：

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

要点：

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

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define INF 0x3f3f3f
int 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);elseprintf("disjoint\n");}return 0;
}