POJ 1125 Stockbroker Grapevine：Floyd-Warshall 多源最短路

題目

有向圖，邊權為傳遞時間。求一個節點作為起點，使其到所有其他節點的最短路中最大值最小。若存在不可達節點輸出 "disjoint"。N ≤ 100。

解法

Floyd-Warshall 算法求所有點對最短路，O(N³) 完全足夠。對每個節點 i，計算 max_j dist[i][j]，取最小者及其對應的最大距離。若最小最大距離 ≥ INF 則輸出 disjoint。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXN = 110;
int dist[MAXN][MAXN];

int main() {
    int n;
    while (scanf("%d", &n) == 1 && 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 t; scanf("%d", &t);
            while (t--) {
                int v, w; scanf("%d%d", &v, &w);
                dist[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 (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        int bestNode = -1, bestMax = INF;
        for (int i = 1; i <= n; i++) {
            int mx = 0;
            for (int j = 1; j <= n; j++) mx = max(mx, dist[i][j]);
            if (mx < bestMax) { bestMax = mx; bestNode = i; }
        }
        if (bestMax >= INF) printf("disjoint\n");
        else printf("%d %d\n", bestNode, bestMax);
    }
    return 0;
}