December Lunchtime 2018 Find Best Path

https://www.codechef.com/LTIME67A/problems/BESTPATH

The distance array D[i] is filled with zero. Then start Bellman-ford, finally D[i] stores the shortest distance between a certain vertex and vertex i. If there are no negative cycles, we can obtain the answer.

When we are repeating Bellman-ford, if a value changes after N iterations, there must be a negative cycles through vertex i. If i is on a negative cycle, the vertices reachable from i are also on a negative cycle.

---

Johnson's algorithm is too slow to pass all cases. If we use SPFA instead of Dijkstra, we got AC.

2N times loop is not enough for detecting negative cycles because there is a counterexample.

1
3 3
2 1 1000000
2 3 -1
3 2 -1

#include <stdio.h>

int T, N, M;
int U[1000], V[1000], W[1000];
long long D[1000], E[1000];
int tau0[1000];
int tau1[1000];
int neg0[1000];
int neg1[1000];

void solve() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &U[i], &V[i], &W[i]);
        U[i]--;
        V[i]--;
    }
    for (int i = 0; i < N; i++) {
        D[i] = 0;
        E[i] = 0;
        tau0[i] = 0;
        tau1[i] = 0;
        neg0[i] = 0;
        neg1[i] = 0;
    }
    for (int i = 1; i <= N * 2; i++) {
        for (int j = 0; j < M; j++) {
            if (D[V[j]] > D[U[j]] + W[j]) {
                D[V[j]] = D[U[j]] + W[j];
                tau0[V[j]] = i;
            }
            if (E[U[j]] > E[V[j]] + W[j]) {
                E[U[j]] = E[V[j]] + W[j];
                tau1[U[j]] = i;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        if (tau0[i] >= N) neg0[i] = 1;
        if (tau1[i] >= N) neg1[i] = 1;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            neg0[V[j]] |= neg0[U[j]];
            neg1[U[j]] |= neg1[V[j]];
        }
    }
    for (int i = 0; i < N; i++) {
        if (!neg0[i] && !neg1[i]) {
            printf("%lld\n", D[i] + E[i]);
        } else {
            puts("INF");
        }
    }
}

int main() {
    scanf("%d", &T);
    while (T--) {
        solve();
    }
}