A ski resort has n stations 0 .. n-1. Runs are directed and never form a loop:
runs[i] = [u, v, cost] goes from u to v. The cost may be negative (some runs pay out a
loyalty rebate). Starting at station src, return a list best of length n where best[i] is
the smallest total cost of reaching station i, or None if it cannot be reached.
Examples
Input: n = 4, runs = [[0,1,5],[0,2,2],[2,1,-4],[1,3,1]], src = 0
Output: [0, -2, 2, -1]
Explanation: 0 -> 2 -> 1 costs 2 - 4 = -2, then 1 -> 3 adds 1.
Input: n = 3, runs = [[1,2,3]], src = 0
Output: [0, None, None]
Constraints
1 <= n <= 10**4,0 <= len(runs) <= 3 * 10**4,-10**4 <= cost <= 10**4- The runs form a directed acyclic graph.
- Target
O(V + E)time.
Goals
- Order the nodes of a DAG topologically
- Relax edges in that order to get shortest paths with negative weights
- Use None for unreachable nodes because -1 is a real distance here