題目描述: 給定一個無向圖,每條邊 (u, v, cnt) 上有 cnt 個新節點(將邊細分)。從節點 0 出發,最多走 maxMoves 步,問能到達多少個節點(包含原始節點和新增節點)?
解題思路:
時間複雜度: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。但原題直接求可達數,不需要二分。