Routes With Discounts and Surcharges
Implement routeCosts
A transport network has one-way links between stops, some with a discount (a negative price). Given the price matrix, compute the cheapest total price from a starting stop to every stop. If a cycle whose total price is negative can be reached, prices can be driven down forever, and you should return an empty array instead.
Dijkstra's algorithm fails with negative prices. Bellman-Ford relaxes every link n − 1 times and then does one more pass to detect a negative cycle.
Example 1:
Input: cost = [[100,4,5,100,100],[100,100,-3,6,100],[100,100,100,4,100],[100,100,100,100,-2],[100,100,100,100,100]], src = 0
Output: [0,4,1,5,3]
Example 2:
Input: cost = [[100,1,100],[100,100,-3],[1,100,100]], src = 0
Output: []
Example 3:
Input: cost = [[100,7],[100,100]], src = 1
Output: [1000,0]
+ 15 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 7 stops numbered 0 … n-1; cost is an n × n matrix: cost[u][v] = 100 means there is no one-way link from u to v, otherwise cost[u][v] (−9 … 9, zero allowed) is the price of the link; a negative price is a discount - ●
cost[u][u] = 100 (no self links) - ●
0 ≤ src < n is the starting stop - ●
Return an array where entry i is the cheapest total price from src to stop i, using 1000 for stops that cannot be reached. If a cycle with a negative total price can be reached from src (prices could then be lowered forever), return an empty array
cost =
src =