Bellman-Ford Route Costs With Credits
Problem statement
DoorDash plans delivery routes between n hubs, labeled 0 to n - 1. Each road is one-way and is given as roads[i] = [from, to, cost]. A cost can be negative: some roads come with a credit, so taking them lowers your total.
You start at hub start. The cost of a route is the sum of the costs of its roads. A route may pass through the same hub more than once.
Return an array dist of length n, where dist[i] is the lowest cost of any route from start to hub i.
- Staying at
startis a route with cost0. - If no route reaches hub
i, setdist[i] = 1000000000. - A negative cycle is a loop of roads whose total cost is below
0. Ifstartcan reach a negative cycle, you could go around it again and again and the cost would keep dropping. In that case, return an empty array. A negative cycle thatstartcannot reach does not change the answer.
Two hubs can be joined by several roads, and a road can start and end at the same hub.
Function
shortestRouteCosts(n: int, roads: int[][], start: int) → int[]Examples
Example 1
n = 4roads = [[0,1,4],[0,2,5],[2,1,-3],[1,3,2],[2,3,6]]start = 0return = [0,2,5,4]The direct road to hub 1 costs 4. Going 0 → 2 → 1 costs 5 + (-3) = 2, which is cheaper, so dist[1] = 2.
Hub 3 is reached by 0 → 2 → 1 → 3 for 2 + 2 = 4. The road 2 → 3 gives 5 + 6 = 11, which is worse.
Hub 2 costs 5. The answer is [0, 2, 5, 4].
Example 2
n = 4roads = [[0,1,3],[2,3,-4],[3,2,1]]start = 0return = [0,3,1000000000,1000000000]From hub 0 you can only reach hub 1, for a cost of 3.
Hubs 2 and 3 form the loop 2 → 3 → 2 with total cost -4 + 1 = -3. That is a negative cycle, but hub 0 cannot reach it, so it does not matter. Hubs 2 and 3 are unreachable and get 1000000000.
Example 3
n = 3roads = [[0,1,1],[1,2,-1],[2,1,-1]]start = 0return = []Hub 0 reaches hub 1, and the loop 1 → 2 → 1 costs -1 + (-1) = -2.
Each extra trip around the loop lowers the cost by 2, so there is no lowest cost. The loop is reachable from hub 0, so the answer is an empty array.
Constraints
1 <= n <= 2000 <= roads.length <= 2000roads[i].length == 3roads[i] = [from, to, cost]with0 <= from, to < n-10^4 <= cost <= 10^40 <= start < n