Submission #1591720

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0; i<n;i++)
using pii = pair<ll,ll>;
ll INF=LLONG_MAX/10;
ll INIT=-10000000000;
signed main(){
    ll n,m; cin>>n>>m;
    vector<vector<pii>>edge(n,vector<pii>());
    rep(i,m){
        ll a,b,c; cin>>a>>b>>c;
        edge[--a].push_back(pii(--b,c));
    }
    vector<ll>d(n,0);
    vector<bool>visit(n,false);
    visit[0]=true;
    while (true) {
        bool update=false;
        rep(v,n)rep(i,edge[v].size()){
            if(visit[v]==false)continue;
            ll next=edge[v][i].first;
            if(visit[next]==false or (d[next]<d[v]+edge[v][i].second)){
                d[next]=d[v]+edge[v][i].second;
                update=true;
                rep(i,edge[next].size()){
                    if(edge[next][i].second+d[next]>d[edge[next][i].first]
                       and visit[edge[next][i].first])
                        return puts("inf")*0;
                }
            if(visit[next]==false)visit[next]=true;
            }
        }
        if(!update)break;
    }
    cout<<d[--n]<<endl;
}

Submission Info

Judge Result