1786. Number of Restricted Paths From First to Last Node

解題說明

C++ 解法

複雜度分析

虛擬碼

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]

其他解法

延伸思考