题意简述

股票经纪人之间的关系形成了一个有向关系网。每个股票经纪人向与他关联的另一个人传递一条谣言需要花费的时间各不相同。A向B传播谣言耗时并不一定等于B向A传播耗时。某经纪人收到谣言后会同时开始向他所有关联的经纪人传播谣言。给定股票经纪人之间的关系网以及每个经纪人向特定经纪人传播消息的耗时，问谣言从哪个股票经纪人开始传播能最快的使整个网所有人知道该谣言，并输出最短耗时。如果存在某经纪人无论如何无法得知该谣言，输出disjoint。

算法分析

某经纪人得知谣言的时间等于从源头到他的传播路径中每对经纪人之间耗时之和。因而本题能够转换为最短路问题。即：一张有向图中因为是多源多点最短路，所以采用floyd算法。

首先用floyd算法求出每两个点间最短路，然后枚举每一个点作为源头，找出由它到达所有点最短路长度的最大值，与当前记录的结果比较，如果比结果耗时低，则替换记录的结果。最后判断，如果求得的最短路长度为初始化的Max，即耗时为无限长（存在点无法到达），则输出disjoint，否则输出记录的结果。

程序样例

#include<stdio.h>
#define MaxI 999999

void floyd(int n, int map[][101]) {
  int i, j, k;
  for (k = 1; k <= n; k++)
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        if (map[i][j] > (map[i][k] + map[k][j]))
          map[i][j] = map[i][k] + map[k][j];
}

void print(int n, int map[][101]) {
  int i, j, maxi, max, ans = MaxI, ansi;
  for (i = 1; i <= n; i++) {
    max = -1;
    for (j = 1; j <= n; j++)
      if (map[i][j] > max) max = map[i][j];
    if (max < ans) {
      ans = max;
      ansi = i;
    }
  }
  if (ans == MaxI) printf("disjoint\n");
  else printf("%d %d\n", ansi, ans);
}

int main() {
  int n, i, j, map[101][101], t1, t2;
  while (scanf("%d", & n), n != 0) {
    for (i = 0; i <= n; i++)
      for (j = 0; j <= n; j++)
        map[i][j] = MaxI;
    for (i = 1; i <= n; i++) {
      for (scanf("%d", & j); j > 0; j--) {
        scanf("%d%d", & t1, & t2);
        map[i][t1] = t2;
      }
      map[i][i] = 0;
    }
    floyd(n, map);
    print(n, map);
  }
  return 0;
}