HardRating 2328

882. Reachable Nodes In Subdivided Graph

graphheap-priority-queueshortest-path

在 LeetCode 上作答 ↗

解題說明

Reachable Nodes In Subdivided Graph

題目描述：給定一個無向圖，每條邊 (u, v, cnt) 上有 cnt 個新節點（將邊細分）。從節點 0 出發，最多走 maxMoves 步，問能到達多少個節點（包含原始節點和新增節點）？

解題思路：

修改版 Dijkstra：在原始圖上用 Dijkstra 算法求出從節點 0 到所有原始節點的最短距離。邊權為 cnt + 1（經過 cnt 個新節點 + 1 步到達對面原始節點）。
如果 dist[v] <= maxMoves，原始節點 v 可達。
對每條邊 (u, v, cnt)，分別計算從 u 端和 v 端能「伸入」邊中多少個新節點：
- 從 u 端能覆蓋 min(cnt, max(0, maxMoves - dist[u])) 個新節點
- 從 v 端能覆蓋 min(cnt, max(0, maxMoves - dist[v])) 個新節點
- 該邊上被覆蓋的新節點數 = min(cnt, fromU + fromV)
答案 = 可達原始節點數 + 所有邊上被覆蓋的新節點數。

C++ 解法

複雜度分析

時間複雜度：O(E log n) — Dijkstra 算法的時間複雜度，E 為邊數，n 為節點數

空間複雜度：O(n + E) — 圖的鄰接表和距離陣列

虛擬碼

1. Build adjacency list with weight = cnt + 1 for each edge
2. Run Dijkstra from node 0 to get shortest distance to all nodes
3. Count reachable original nodes: dist[i] <= maxMoves
4. For each edge (u, v, cnt):
   a. fromU = min(cnt, max(0, maxMoves - dist[u]))
   b. fromV = min(cnt, max(0, maxMoves - dist[v]))
   c. Add min(cnt, fromU + fromV) to answer
5. Return total count

其他解法

BFS 在細分圖上：直接在細分後的圖上做 BFS，但節點數可能爆炸（每條邊最多 10^4 個新節點），不切實際。
二分搜尋 + Dijkstra：如果問題變成「給定要覆蓋的節點數，求最少需要多少步」，可以二分搜尋步數，對每個候選步數跑 Dijkstra。但原題直接求可達數，不需要二分。

延伸思考

如果圖是有向的，答案會有什麼不同？
如果可以從任意節點出發（而不只是節點 0），如何找到能覆蓋最多節點的起點？
如果每條邊上的新節點有不同的權重，該如何修改算法？

Reachable Nodes In Subdivided Graph — CaffeCode