思路与算法

用Floyd求任意两站最短耗时。初始化自己到自己为0，重边取最小；最终若某站与1不连通输出-1，否则输出第1行距离的最大值。

正确性说明

任一站收到信息都必须经过一条从1到它的路径，故不早于最短距离。信使可同时沿所有必要路径转发，最短距离可以实现。所有站收到的最早时刻因而等于这些最短距离的最大值；不可达站永远无法收到。

复杂度

初始化O(n²)、读边O(m)、Floyd O(n³)、汇总O(n)，总O(n³+m)，空间O(n²)。

易错点

双向线路要更新两边；重边取小。零耗时、自环、单站均合法。距离用64位并避免无穷加法溢出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    const long long INF = 4000000000000000000LL;
    vector<vector<long long>> d(n, vector<long long>(n, INF));
    for (int i = 0; i < n; i++)
        d[i][i] = 0;
    for (int i = 0, u, v; i < m; i++) {
        long long w;
        cin >> u >> v >> w;
        --u;
        --v;
        d[u][v] = d[v][u] = min(d[u][v], w);
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    long long ans = *max_element(d[0].begin(), d[0].end());
    cout << (ans == INF ? -1 : ans) << '\n';
}