Submission #1285647

---

Source Code Expand

#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF 1000000000000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int qx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int qy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

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

int main(void) {
	ll N, M;
	cin>>N>>M;
	vector<__int128> d(N, -INF);
	vector<edge> es(M);
	REP(i, M) {
		ll a, b, c;
		cin>>a>>b>>c;
		--a;
		--b;
		edge e = {a, b, c};
		es[i] = e;
	}
	d[0] = 0;
	__int128 cnt = 0;
	ll cnthoge = 0;
	bool f = false;
	while(true) {
		if(f || d[N - 1] > 10000000000000 || d[N - 1] < -10000000000000 && d[N - 1] != -INF || cnt > 10000) {
			f = true;
			break;
		}
		bool update = false;
		REP(i, es.size()) {
			edge e = es[i];
			if(d[e.from] != -INF && d[e.to] < d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				if(e.to == N - 1) ++cnthoge;
				if(d[e.to] > 10000000000000 || d[e.to] < -10000000000000) {
					f = true;
					break;
				}
				update = true;
			}
		}
		if(!update) break;
		++cnt;
	}
	if(f && cnthoge > 1000)cout<<"inf"<<endl;
	else {
		if(d[N - 1] == -INF) {
			cout<<0<<endl;
		} else {
			ll ans = d[N - 1];
			cout<<ans<<endl;
		}
	}
}

Submission Info

Judge Result