Submission #1531678

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

const ll INF = (1LL << 50);

int main() {
    int N, M;
    cin >> N >> M;

    const int MAX_N = 2000;
    const int MAX_M = 3000;

    int a[MAX_M], b[MAX_M];
    ll  c[MAX_M];

    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i] >> c[i];

        a[i]--;
        b[i]--;
        c[i] = -c[i];
    }

    ll dist[MAX_N];
    for (int i = 0; i < N; i++) dist[i] = INF;
    
    dist[0] = 0;
    for (int loop = 0; loop < N - 1; loop++) {
        for (int i = 0; i < M; i++) {
            if (dist[a[i]] == INF) continue;

            if (dist[b[i]] > dist[a[i]] + c[i]) {
                dist[b[i]] = dist[a[i]] + c[i];
            }
        }
    }

    ll ans = -dist[N - 1];

    bool negative[N];
    for (int i = 0; i < N; i++) negative[i] = false;

    for (int loop = 0; loop < N; loop++) {
        for (int i = 0; i < M; i++) {
            if (dist[a[i]] == INF) continue;

            if (dist[b[i]] > dist[a[i]] + c[i]) {
                dist[b[i]] = dist[a[i]] + c[i];
                negative[b[i]] = true;
            }

            if (negative[a[i]]) negative[b[i]] = true;
        }
    }

    if (negative[N - 1]) cout << "inf" << endl;
    else cout << ans << endl;

    return 0;
}

Submission Info

Judge Result