POJ 1125 Stockbroker Grapevine：Floyd-Warshall 求圖傳播最短時間

題目大意

n (≤100) 個股票經紀人，每人可向特定其他人傳遞消息，需時 t。
求：選擇一個起始人，使得消息傳達給**所有人**的**最長最短路徑時間**最小。輸出該人編號與時間。若圖不連通，輸出 disjoint。

模型轉化

• 有向加權圖，邊權 = 傳遞時間。
• 需求 = **圖的中心**：min_{v} max_{u} dist(v,u)。
• n ≤ 100 → **Floyd-Warshall** O(n³) 完美適用。

算法流程

1. 初始化 dist[i][j] = INF，dist[i][i] = 0。
2. 讀入邊，dist[u][v] = time（可能有多條邊，取最小）。
3. Floyd 三重循環更新全序對最短路。
4. 對每個點 i 計算 maxDist = max_j dist[i][j]。
5. 選 maxDist 最小的點，輸出編號與時間；若存在 INF 則 disjoint。

完整代碼

#include 
using namespace std;

const int INF = 1e9;
const int MAXN = 105;
int dist[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, caseNo = 0;
    while (cin >> n, n) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = (i == j) ? 0 : INF;

        for (int i = 1; i <= n; ++i) {
            int cnt; cin >> cnt;
            while (cnt--) {
                int v, t; cin >> v >> t;
                dist[i][v] = min(dist[i][v], t);
            }
        }

        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[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 (dist[i][j] == INF) { mx = INF; break; }
                mx = max(mx, dist[i][j]);
            }
            if (mx < bestTime) {
                bestTime = mx;
                best = i;
            }
        }

        if (best == -1) cout << "disjoint\n";
        else cout << best << ' ' << bestTime << '\n';
    }
    return 0;
}

複雜度分析

• 時間：O(n³) = 10⁶ 操作，極快。
• 空間：O(n²) = 10⁴ 整數。

關鍵細節

1. 多邊取最小：輸入可能重複給出同向邊，用 min 保留最短。
2. 有向圖：傳遞關係單向，不可對稱賦值。
3. 斷圖判斷：Floyd 後若任意 dist[i][j] == INF，該起始點不可行。
4. 輸出格式：編號 時間，無冒號、無額外空格。

測試樣例

輸入：
3
2 2 5 3 10
1 3 5
0
0
輸出：
2 10

解析：1→2(5), 1→3(10)；2→3(5)；3 無出邊。
從 1 出發：到 2 需 5，到 3 需 10 → 最長 10。
從 2 出發：到 3 需 5，到 1 不可達 → disjoint。
從 3 出發：不可達任何人。
∴ 答案 2 10。

總結

POJ 1125 是 **Floyd-Warshall 找圖中心** 的教科書級例題。
掌握：鄰接矩陣初始化 → 三重循環松弛 → 掃描每行最大值 → 取全局最小。
n ≤ 100 時 Floyd 碾壓 Dijkstra×n / SPFA，代碼最短、最不易錯。