POJ 1125 Stockbroker Grapevine：Floyd-Warshall 求最優傳聞源

問題描述

有 N (≤100) 個股票經紀人，形成有向加權圖。邊 i→j 權重為傳遞消息所需時間（1~10 分鐘）。選擇一個起始經紀人，使消息傳遍所有人的最長時間（即從該點到所有點的最短路徑中最大值）最小。若圖不連通（存在不可達點），輸出 disjoint。

解法：Floyd-Warshall 全源最短路

N ≤ 100，Floyd O(N³) 完全可行。步驟：

1. 初始化距離矩陣 dis[i][j]：i=j 為 0，有邊為給定權重，無邊為 INF。
2. 三重循環 k, i, j 松弛：dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])。
3. 對每個點 i，計算 max_j dis[i][j]。若存在 INF，圖不連通。
4. 選擇 max_j dis[i][j] 最小的點作為答案。

關鍵細節

• 圖為有向圖，dis[i][j] 不一定等於 dis[j][i]。
• INF 取值需大於最大可能路徑和（100*10=1000），如 1e9。
• 輸入以 0 結束，多組測試案例。

參考代碼 (C++)

#include 
#include 
#include 
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int dis[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n, n) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dis[i][j] = (i == j) ? 0 : INF;
        for (int i = 1; i <= n; ++i) {
            int cnt; cin >> cnt;
            for (int k = 0; k < cnt; ++k) {
                int v, w; cin >> v >> w;
                dis[i][v] = w;
            }
        }
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    if (dis[i][k] + dis[k][j] < dis[i][j])
                        dis[i][j] = dis[i][k] + dis[k][j];
        int best = -1, bestTime = INF;
        for (int i = 1; i <= n; ++i) {
            int mx = 0;
            for (int j = 1; j <= n; ++j) {
                if (dis[i][j] == INF) { mx = INF; break; }
                mx = max(mx, dis[i][j]);
            }
            if (mx < bestTime) {
                bestTime = mx;
                best = i;
            }
        }
        if (bestTime == INF) cout << "disjoint\n";
        else cout << best << ' ' << bestTime << '\n';
    }
    return 0;
}

複雜度分析

時間 O(T * N³)，N=100 時約 10⁶ 操作/測試案例，極快。空間 O(N²)。

總結

• 小規模全源最短路首選 Floyd，代碼簡短且不易出錯。
• 注意有向圖特性與不連通判斷。
• 輸出格式：編號與時間空格分隔，disjoint 全小寫。