Submission #1696712

---

Source Code Expand

#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long LL;
const LL INF = 1LL << 60;
const LL MOD = 1000000007LL;
using namespace std;
typedef pair<int, int> P;
vector<P> G[1000];
LL dist[1000];
int main() {
	int N, M;
	cin >> N >> M;
	rep(i, M) {
		int a, b, c;
		cin >> a >> b >> c; a--; b--;
		G[a].push_back(P(b, -c));
	}
	fill((LL*)dist, (LL*)(dist + N), INF);
	dist[0] = 0;
	rep(k, N - 1) {
		bool update = 0;
		rep(i, N) {
			rep(j, G[i].size()) {
				int to = G[i][j].first;
				int cost = G[i][j].second;
				if (dist[to] > dist[i] + cost) {
					dist[to] = dist[i] + cost;
					update = 1;
				}
			}
		}
		if (!update) break;
	}
	bool inf = 0;
	rep(k, N - 1) {
		bool update = 0;
		rep(i, N) {
			rep(j, G[i].size()) {
				int to = G[i][j].first;
				int cost = G[i][j].second;
				if (dist[to] > dist[i] + cost) {
					if (to == N - 1) inf = 1;
					dist[to] = dist[i] + cost;
					update = 1;
				}
			}
		}
		if (!update) break;
	}
	if (inf) {
		cout << "inf" << endl;
	}
	else {
		cout << -dist[N - 1] << endl;
	}
}

Submission Info

Judge Result