Bellman–Ford Algorithm

Practice this coding question on Coding Gurukul.

Problem statement

Given a directed weighted graph and source s, use Bellman–Ford to find the shortest distance to every vertex. Edge weights may be negative. If a negative-weight cycle is reachable from s, print NEGATIVE CYCLE only. Ignore negative cycles that cannot be reached from s. Otherwise, print distances in vertex order and INF for unreachable vertices. Self-loops and repeated edges are allowed. Use signed 64-bit distances and O(n*m) time. Worked example The path 0→1→2 costs 4-6=-2, less than the direct cost 5. Vertex 3 is unreachable. Print 0 4 -2 INF.

Input format

First line: n m s. Next m lines: directed edge u v w.

Output format

Print NEGATIVE CYCLE, or n space-separated distances/INF tokens in vertex order.

Constraints

1 <= n <= 500; 0 <= m <= 3000; 0 <= s,u,v < n; -10^9 <= w <= 10^9.

Sample input

4 3 0
0 1 4
1 2 -6
0 2 5

Sample output

0 4 -2 INF

Sign in to run or submit a solution in C++, Java or Python.