Submission #2214920

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

struct edge{ ll from,to,cost; };
const ll INF=1e18;

void solve(int N,int M,vector<edge>& es)
{
    vector<ll> dist(N,INF);
    dist[0]=0;

    for(int i=0;i<N;i++){
    	for(auto e:es){
    	    if(dist[e.from]==INF) continue;
    	    if(dist[e.to]>dist[e.from]+e.cost){
    		dist[e.to]=dist[e.from]+e.cost;
    	    }
    	}
    }
    bool flag = false;
    for(int i=0;i<N;i++){
    	for(auto e:es){
    	    if(dist[e.from]==INF) continue;
    	    if(dist[e.to]>dist[e.from]+e.cost){
        		dist[e.to]=dist[e.from]+e.cost;
                if(e.to == N-1){
                    flag = true;
                }
    	    }
    	}
        if(flag) break;
    }

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

signed main()
{
    ll N,M; cin>>N>>M;
    vector<edge> es(M);
    for(int i=0;i<M;i++){
    	ll a,b,c; cin>>a>>b>>c; a--,b--;
    	es[i]=(edge){a,b,-c};
    }
    solve(N,M,es);
    return 0;
}

Submission Info

Judge Result