Submission #1440174

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m; cin>>n>>m;

    vector<vector<int>> g(n);
    vector<vector<long>> cost(n, vector<long>(n));

    while (m--) {
        long a, b, c; cin>>a>>b>>c;
        --a, --b;
        g[a].push_back(b);
        cost[a][b]=-c;
    }

    const long inf=LONG_MAX;
    vector<long> d(n, inf);
    d[0]=0;
    int cnt=0;
    bool has_negative_loop=false;
    for(int cnt=0; cnt<n+n; ++cnt) {
        for(int v=0; v<n; ++v) {
            for(int u: g[v]) {
                if (d[v]==inf or d[u]<=d[v]+cost[v][u]) continue;
                d[u]=d[v]+cost[v][u];
                if (cnt>=n and u==n-1) has_negative_loop=true;
            }
        }
    }
    if (has_negative_loop)
        cout<<"inf"<<endl;
    else
        cout<<-d[n-1]<<endl;
}

Submission Info

Judge Result