Submission #2214871

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

struct edge{
    ll to, from, cost;
};

const int MAX = 2010;
const ll INF = 1e10;
edge es[MAX];

int N, M;
ll dist[MAX];

bool neg_loop(int s, int t){
    for(int i=0;i<N;i++) dist[i] = INF;
    dist[s] = 0;
    for(int i=0;i<2*N;i++){
        for(int j=0;j<M;j++){
            edge e = es[j];
            if(dist[e.from] != INF && dist[e.to] > dist[e.from] + e.cost){
                dist[e.to] = dist[e.from] + e.cost;

                if(i >= N-1 && e.to == t) return true;
            }
        }
    }
    return false;
}

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

    for(int i=0;i<M;i++){
        ll a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        es[i].from = a;
        es[i].to = b;
        es[i].cost = -c;
    }

    bool flag = neg_loop(0,N-1);

    if(flag){
        cout << "inf" << endl;
    }else{
        cout << -dist[N-1] << endl;
    }
}

Submission Info

Judge Result