Skills101
← All coding problems

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 m lines: 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).

Loading editor…

Log in to run and submit your code — it's free.