Shortest paths with negative edges

Dijkstra fails when an edge is negative. Bellman–Ford does not, and it can even tell when no shortest path exists.

What to build

The Bellman–Ford algorithm, from vertex 0, on a directed graph.

Requirements

Relax every edge n - 1 times.
Only relax an edge when its start vertex has been reached.
Print negative cycle if a negative cycle can be reached from vertex 0.
Otherwise print the distances, using INF for vertices that cannot be reached.

Input

The first line has n and m. Each of the next m lines has a directed edge u v w.

Output

One line: the n distances separated by spaces, or negative cycle.

Constraints

1 ≤ n ≤ 100, 0 ≤ m ≤ 1000 and -1000 ≤ w ≤ 1000.

Example

Input:

Output:

0 -1 2 -2 1

Why it works

A shortest path visits at most n − 1 edges, and round k gets every path of k edges right. If an edge can still improve after n − 1 rounds, a route keeps getting shorter by going round a negative cycle.

Examples

Example 1 · Input

Expected output

0 -1 2 -2 1

Example 2 · Input

Expected output

negative cycle

Hints

Hint 1

Repeat `n - 1` times: go through every edge and relax it.

Hint 2

Skip an edge whose start has not been reached, or an unreachable cycle would be reported by mistake.

Hint 3

After that, if any edge can still be relaxed, there is a negative cycle that can be reached.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>
#define INF 1000000000

int main(void) {
    int n, m, u[1000], v[1000], w[1000], dist[100];
    scanf("%d %d", &n, &m);
    for (int e = 0; e < m; e++) scanf("%d %d %d", &u[e], &v[e], &w[e]);
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[0] = 0;
    for (int round = 0; round < n - 1; round++)
        for (int e = 0; e < m; e++)
            if (dist[u[e]] != INF && dist[u[e]] + w[e] < dist[v[e]])
                dist[v[e]] = dist[u[e]] + w[e];
    for (int e = 0; e < m; e++) {
        if (dist[u[e]] != INF && dist[u[e]] + w[e] < dist[v[e]]) {
            printf("negative cycle\n");
            return 0;
        }
    }
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) printf("INF ");
        else printf("%d ", dist[i]);
    }
    printf("\n");
    return 0;
}

Lesson: Shortest paths: Dijkstra and Floyd–Warshall →