Submission #1690126

---

Source Code Expand

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
 
#define INF 2147483647
#define LINF 9223372036854775807
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
 
typedef long long ll;
typedef pair<ll, int> P;
 
struct edge {int to;ll cost; edge(int t,ll c):to(t),cost(c){}};
 
int n,m;
vector<edge> g[1000];
ll d[1000];
 
bool bellman_ford() {
	REP(i,n) d[i]=LINF;
	d[0]=0;
	REP(i,n+1) {
		REP(v,n+1) {
			REP(k,g[v].size()) {
				edge e=g[v][k];
				if(d[v]!=LINF&&d[e.to]>d[v]+e.cost) {
					d[e.to]=d[v]+e.cost;
					if(i==n) return true;
				}
			}
		}
	}
	return false;
}
 
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin>>n>>m;
	REP(i,m) {
		int a,b; ll c; cin>>a>>b>>c; a--; b--;
		g[a].push_back(edge(b,-c));
	}
	if(bellman_ford()) cout<<"inf"<<endl;
	else cout<<-d[n-1]<<endl;
 
	return 0;
}

Submission Info

Judge Result