Shortest Paths with Negative Edges (Bellman-Ford)
mediumGraphs II+20 XPTime limit 3s
A trader travels between n markets along one-way routes. Route u v w changes her money by w rupees in cost — and w may be negative (a route where she earns money). Find the minimum total cost from market s to every market.
If she can reach a negative cycle (a loop whose total cost is below zero, so the cost could be pushed down forever), print NEGATIVE CYCLE instead.
Input:
- line 1:
n m s - next
mlines:u v w
Output: either NEGATIVE CYCLE, or one line with n values: the minimum cost from s to markets 1 … n (0 for s, INF for a market that cannot be reached).
Constraints: 1 ≤ n ≤ 500, 0 ≤ m ≤ 5000, −10⁴ ≤ w ≤ 10⁴, u ≠ v; several routes may join the same pair. A negative cycle that s cannot reach does not matter.
Think about it: Dijkstra breaks with negative edges. Bellman-Ford relaxes every edge n − 1 times — enough for any shortest path, which uses at most n − 1 edges. If one more round can still improve some distance, a reachable negative cycle exists. O(n · m).
Sample input 1
4 4 1 1 2 4 1 3 2 3 2 -3 2 4 1
Sample output 1
0 -1 2 0
Sample input 2
3 3 1 1 2 1 2 3 -2 3 2 1
Sample output 2
NEGATIVE CYCLE
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).