Submission #1281207

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, long long>> arr[1100];

const long long INF = LLONG_MAX - 2000000000LL;
int isReached[1100];
int isUsed[1100];
long long dis[1100];
int cnt[1100];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		long long c;
		cin >> a >> b >> c;
		arr[a].emplace_back(b, c);
	}
	
	dis[1] = 0;
	isReached[1] = 1;
	
	while (true) {
		int tar = -1;
		for (int i = 1; i <= n; ++i) {
			if (isReached[i] == 1 && isUsed[i] == 0) {
				if (tar == -1) tar = i;
				else if(dis[i] > dis[tar]) tar = i;
			}
		}
		if (tar == -1) break;
		isUsed[tar] = 1;
		for (const auto &p : arr[tar]) {
			long long ndis = min(dis[tar] + p.second, INF);
			int nxt = p.first;
			if (isReached[nxt] == 0) {
				isReached[nxt] = 1;
				dis[nxt] = ndis;
			} else if(ndis > dis[nxt]) {
				dis[nxt] = ndis;
				++cnt[nxt];
				isUsed[nxt] = 0;
				if (cnt[nxt] > n) {
					dis[nxt] = INF;
				}
			}
		}
	}
	
	if (dis[n] == INF) puts("inf");
	else cout << dis[n] << endl;
	
	return 0;
}

Submission Info

Judge Result