ZOJ 3396 Conference Call：三點最小連通成本的 Floyd + 枚舉中轉點

問題重述

n 部電話，m 個中轉站（m≤500），l 條有線連接。每部電話連接最近的中轉站。
三方會議信號從撥號端出發，經中轉站到達另外兩部電話。求三部電話 a,b,c 的最小總傳輸成本（邊權和）。多查詢 q≤50。

關鍵建模：中轉站圖上的最小「Y」型樹

三部電話對應中轉站 A,B,C。會議連接本質是找一個中轉站 X（可為 A/B/C 或其他），使 dist(X,A)+dist(X,B)+dist(X,C) 最小。
證明：最優連通子圖必為一棵樹，三葉子節點為 A,B,C，內部節點度數 ≥2，唯一拓撲為一個中心 X 三條鏈。故枚舉所有 X 即可。

算法流程

1. 讀入中轉站圖，Floyd-Warshall 算出任意兩站點最短路 dist[u][v]。
2. 每部電話映射到其所屬中轉站 root[phone]。
3. 查詢 (x,y,z)：
     A=root[x], B=root[y], C=root[z]
  ans = min_{i=1..m} (dist[i][A]+dist[i][B]+dist[i][C])
4. 若 ans ≥ INF 輸出 Impossible。

完整 C++ 代碼

#include 
using namespace std;
const int INF = 1e8;
const int MAXM = 505;

int dist[MAXM][MAXM];
int root[10005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n, l, caseNo = 1;
    while(cin >> m >> n >> l) {
        // 初始化
        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<=m;++i) cin >> root[i];
        for(int i=0;i> u >> v >> w;
            dist[u][v] = dist[v][u] = min(dist[u][v], w);
        }

        // Floyd
        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 q; cin >> q;
        cout << "Case #" << caseNo++ << '\n';
        for(int qq=1; qq<=q; ++qq) {
            int x,y,z; cin >> x >> y >> z;
            int A=root[x], B=root[y], C=root[z];
            int best = INF;
            for(int i=1;i<=n;++i) {
                if(dist[i][A]==INF || dist[i][B]==INF || dist[i][C]==INF) continue;
                best = min(best, dist[i][A]+dist[i][B]+dist[i][C]);
            }
            cout << "Line " << qq << ": ";
            if(best==INF) cout << "Impossible to connect!\n";
            else cout << "The minimum cost for this line is " << best << ".\n";
        }
    }
    return 0;
}

複雜度

• Floyd：O(n³) = 1.25e8（n=500），10s 時限 C++ 優化編譯可過。
• 查詢：O(q·n) = 2.5e4。

常見坑點

• 只枚舉 A,B,C 兩兩最短路之和（如 AB+BC），忽略中間點 X 可為其他站點，導致 WA（樣例圖即為反例）。
• 多測試用例之間未重置 dist 數組。
• 邊可能重複，取 min。
• 輸出格式嚴格對應樣例（Case #i:, Line j:, 句號）。

優化提示

若 n 更大，可對每個查詢點跑 3 次 Dijkstra（O(q·(m log n))），但本題 n=500 Floyd 更簡潔且常數小。