MediumRating 2079

1786. Number of Restricted Paths From First to Last Node

dynamic-programminggraphtopological-sortheap-priority-queueshortest-path

解題說明

Number of Restricted Paths From First to Last Node

題目描述：給定一個加權無向圖，定義「受限路徑」為從節點 1 到節點 n 的路徑，且路徑上每一步都滿足 dist[next] < dist[current]，其中 dist[v] 是從節點 v 到節點 n 的最短距離。求受限路徑的數量，取模 10^9 + 7。

解題思路：先用 Dijkstra 從節點 n 出發計算所有節點到 n 的最短距離。然後將所有節點按 dist 值升序排列（等價於拓撲排序），用 DP 計算路徑數。dp[n] = 1，對每個節點 u（按 dist 升序），將 dp[u] 累加到所有鄰居 v（滿足 dist[v] > dist[u]）的 dp[v] 中。最終答案為 dp[1]。

C++ 解法

複雜度分析

時間複雜度：O(E log V) — Dijkstra 為主要開銷，DP 部分為 O(V + E)。

空間複雜度：O(V + E) — 鄰接表、距離陣列和 DP 陣列。

虛擬碼

1. Build adjacency list from edges
2. Run Dijkstra from node n to compute dist[v] for all v
3. Sort all nodes by dist ascending
4. Init dp[n] = 1
5. For each node u in sorted order:
   a. For each neighbor v of u:
      - If dist[v] > dist[u]: dp[v] += dp[u] (mod)
6. Return dp[1]

其他解法

記憶化 DFS：從節點 1 出發做 DFS，只走 dist 遞減的鄰居，用記憶化避免重複計算。邏輯等價但可能遇到遞迴深度問題。

BFS 拓撲排序：將 dist 嚴格遞減的邊看作 DAG 的有向邊，用標準拓撲排序 + DP 計算路徑數。明確建立 DAG 後更易理解。

延伸思考

若要找出字典序最小的受限路徑，如何修改演算法？
若邊權可能為負，Dijkstra 不適用，該用什麼演算法替代？
若受限路徑的條件改為 dist[next] <= dist[current]（允許相等），問題如何變化？

Number of Restricted Paths From First to Last Node — CaffeCode