773. Negative Toll Roads
A freight network has n depots numbered 0 to n - 1 joined by one-way roads edges[i] = [from, to, toll]. A toll may be negative: that road pays the driver a rebate, and the cost of a route is the sum of its tolls. Starting from depot src, compute the cheapest total toll to every depot.
Return an array of length n whose entry j is the cheapest toll from src to depot j, using 1000000000 for depots that cannot be reached. If a loop of roads with negative total toll can be reached from src, costs are unbounded, so return an empty array instead. Negative loops that src can never reach are ignored.
Example 1
- Input:
- n = 4edges = [[0,1,4],[0,2,5],[2,1,-3],[1,3,2]]src = 0
- Output:
- [0,2,5,4]
- Explanation:
Depot 1 is cheaper through depot 2 (5 - 3 = 2) than directly (4), and depot 3 then costs 2 + 2 = 4, giving [0, 2, 5, 4].
Example 2
- Input:
- n = 3, edges = [[0,1,1],[1,2,-2],[2,1,1]], src = 0
- Output:
- []
- Explanation:
The loop 1 -> 2 -> 1 has total toll -2 + 1 = -1 and depot 1 is reachable from depot 0, so costs are unbounded and the result is empty.
Example 3
- Input:
- n = 3, edges = [[0,1,2]], src = 0
- Output:
- [0,2,1000000000]
- Explanation:
Depot 2 has no road leading to it from depot 0, so its entry is the unreachable marker 1000000000.
Constraints
- 1 ≤ n ≤ 1000
- 0 ≤ edges.length ≤ 5000
- 0 ≤ from, to, src < n; self-loops and parallel roads are allowed
- -104 ≤ toll ≤ 104
- Without a reachable negative loop every cheapest cost has absolute value below 108
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(n * m)
- Space
- O(n)