题意分析

题目要求我们找到一个最佳的经纪人作为传播谣言的起点，使得谣言能够以最快的速度传播到整个经纪人社区。每个经纪人都有自己的“可信来源”联系人，并且向每个联系人传递谣言需要一定的时间。我们需要根据给定的经纪人数量以及每个经纪人的联系人信息（联系人编号和传递时间），计算出最佳的起始经纪人编号以及谣言传播到最后一个人的时间。如果网络不连通（存在无法到达的经纪人），则输出 disjoint。

解题思路

1. 输入处理：读取经纪人数量 N，如果 N 为 0 则结束程序。对于每个经纪人，读取其联系人数量 a 以及 a 对联系人编号 b 和传递时间 c，并将这些信息存储在路径矩阵 map 中。初始化路径矩阵时，将自身到自身的距离设为 0，其他距离设为一个较大的值 myInf 表示不可连通。
2. Floyd 算法：使用 Floyd 算法计算任意两个经纪人之间的最短路径。Floyd 算法的核心是通过三重循环，对于每个中间节点 k，检查 map[i][k] + map[k][j] 是否小于 map[i][j]，如果是，则更新 map[i][j]。
3. 寻找最佳起始经纪人：遍历每个经纪人 i，找到从该经纪人到其他所有经纪人的最长传播时间 temp。然后比较所有经纪人的最长传播时间，找到其中最小的 ans，对应的经纪人编号即为最佳起始经纪人 curIndex。
4. 判断网络连通性：如果在寻找最佳起始经纪人的过程中，发现存在某个经纪人到其他经纪人的距离为 myInf，则说明网络不连通，输出 disjoint。否则，输出最佳起始经纪人编号 curIndex 和谣言传播到最后一个人的时间 ans。

代码实现

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

const int MAXN = 100 + 5;

const int myInf = 999999;   // 标记为不可连通

int map[MAXN][MAXN]; // 路径矩阵，map[i][j]代表从i到j的最短路径

int main()
{
    int N;
    while (~scanf("%d", &N) && N != 0)
    {
        int i, j;
        for (i = 1; i <= N; ++i)
            for (j = 1; j <= N; ++j)   // Floyd算法一定要先初始化
            {
                if (i == j)
                    map[i][j] = 0;
                else
                    map[i][j] = myInf;
            }
        for (i = 1; i <= N; ++i)
        {
            int a;
            scanf("%d", &a);
            for (j = 1; j <= a; ++j)
            {
                int b, c;
                scanf("%d %d", &b, &c);
                map[i][b] = c;
            }
        }
        int k;
        for (k = 1; k <= N; ++k)  // Floyd算法的核心代码只有5行，三重循环+DP
            for (i = 1; i <= N; ++i)
                for (j = 1; j <= N; ++j)
                    if (map[i][k] + map[k][j] < map[i][j])
                        map[i][j] = map[i][k] + map[k][j];
        int ans = myInf, curIndex = 0;
        bool isConnected = true;
        for (i = 1; i <= N; ++i)
        {
            int temp = -1;
            for (j = 1; j <= N; ++j)
            {
                if (map[i][j] == myInf)
                {
                    isConnected = false;
                    break;
                }
                if (map[i][j] > temp)
                    temp = map[i][j];
            }
            if (temp < ans)
            {
                ans = temp;
                curIndex = i;
            }
        }
        if (isConnected)
            printf("%d %d\n", curIndex, ans);
        else
            printf("disjoint\n");
    }
    return 0;
}