題目描述: 給定一個有向加權圖,有 n 個節點和 m 條邊。給定三個節點 src1、src2、dest。找到一個最小權重的子圖,使得 src1 和 src2 都能到達 dest。回傳最小總邊權,若不可能則回傳 -1。
解題思路: 關鍵觀察:最優解中,從 src1 到 dest 的路徑和從 src2 到 dest 的路徑會在某個中間節點 m 合流,之後共用從 m 到 dest 的路徑。
因此,答案 = min over all nodes m of: dist1[m] + dist2[m] + distR[m],其中:
步驟:
時間複雜度:O((n + m) log n) — 三次 Dijkstra,每次 O((n + m) log n)。
空間複雜度:O(n + m) — 正向圖、反向圖各 O(m),距離陣列 O(n)。
1. Build forward adjacency list and reverse adjacency list. 2. Run Dijkstra from src1 on forward graph → dist1[]. 3. Run Dijkstra from src2 on forward graph → dist2[]. 4. Run Dijkstra from dest on reverse graph → distR[]. 5. For each node m: if all three distances are finite, candidate = dist1[m] + dist2[m] + distR[m]. 6. Return minimum candidate, or -1 if none.
Steiner 樹精確演算法:此問題本質是求 {src1, src2, dest} 三個終端的最小 Steiner 樹。可用 DP on subsets:dp[S][v] 表示連接終端子集 S 且以 v 為根的最小代價。時間複雜度 O(3^k * n + 2^k * m log n),k=3 時為 O(n + m log n)。但對此題三源合流的觀察更簡潔。
列舉合流邊:不枚舉合流節點,而是枚舉合流邊 (u, v, w)。分別考慮 src1 和 src2 在邊的哪一端合流。但這比枚舉節點更複雜且無效率優勢。