股票经纪人要在一群人n 个人的编号为 0~n-1中散布一个传言传言只在认识的人中间传递。题目中给出了人与人的认识关系以及传言在某两个认识的人中传递所需要的时间。编写程序求出以哪个人为起点可以在耗时最短的情况下让所有人收到消息。提示：利用Floyd算法求所有人之间传递消息的最短时间即最短路径长度然后求每个人i传递消息到其他所有人的最短时间的最大值改时间表示从i开始传递消息到其他所有人所需时间再在这些

#include <stdio.h> #define INF 0x3f3f3f3f // 定义一个无穷大的数

int n, m; // n为人的个数，m为认识关系的个数 int map[1010][1010]; // 存储认识关系以及传递时间的矩阵

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

int main() { scanf("%d %d", &n, &m);

int i, j, k;
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        if (i == j) {
            map[i][j] = 0; // 自己到自己的时间为0
        } else {
            map[i][j] = INF; // 其他的时间先设为无穷大
        }
    }
}

int a, b, c;
for (i = 0; i < m; i++) {
    scanf("%d %d %d", &a, &b, &c);
    map[a][b] = map[b][a] = c; // 注意是无向图
}

floyd(); // 求所有人之间传递消息的最短时间

int max = INF, min = -1;
for (i = 0; i < n; i++) {
    max = -1;
    for (j = 0; j < n; j++) {
        if (map[i][j] > max) {
            max = map[i][j];
        }
    }
    if (max < min || min == -1) {
        min = max;
        k = i;
    }
}

printf("%d\n", k);

return 0;