Submission #1285316

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000, MAX_M = 2000, INDEX = 1;
const int MAX_C = 1000000000;
const long long INF = (long long)(MAX_N) * (long long)(MAX_C) + 1;

int n, m, a[MAX_M + INDEX], b[MAX_M + INDEX], c[MAX_M + INDEX];
long long d[2][MAX_N + INDEX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    cin >> n >> m;

    for (int j = 1; j <= m; j++) {
        cin >> a[j] >> b[j] >> c[j];
    }

    for (int i = 1; i <= n; i++) {
        d[0][i] = -INF;
    }

    d[0][1] = 0;

    for (int k = 1; k <= 2 * n; k++) {
        for (int i = 1; i <= n; i++) {
            d[1][i] = d[0][i];
        }

        for (int j = 1; j <= m; j++) {
            d[1][b[j]] = min(INF, max(d[1][b[j]], d[0][a[j]] + c[j]));
        }

        for (int i = 1; i <= n; i++) {
            if (k >= n && d[1][i] > d[0][i]) {
                d[1][i] = INF;
            }

            d[0][i] = d[1][i];
        }
    }

    if (d[0][n] < INF) {
        cout << d[0][n] << endl;
    } else {
        cout << "inf" << endl;
    }

    return 0;
}

Submission Info

Judge Result