Loading...
Loading...
Loading...
A shipping network has n hubs and m one-way routes "a b w". The cost w may be negative, because some routes give a refund. Starting at hub 1, print the lowest cost to reach every hub. Print INF for a hub that cannot be reached. If a loop with a total cost below zero can be reached from hub 1, print only NEGATIVE CYCLE.
Example 1
Input
4 4 1 2 4 1 3 5 3 2 -3 2 4 2
Output
0 2 5 4
Hub 2 costs 5 - 3 = 2 through hub 3.
Example 2
Input
3 3 1 2 1 2 3 -2 3 2 1
Output
NEGATIVE CYCLE
The loop 2, 3, 2 costs -1.
Try the problem first. Open one hint at a time.
Relax every route n - 1 times, starting from hub 1 with cost 0.
Run one more pass. If any distance still drops, a negative loop is reachable.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor