Submission #1609041

---

Source Code Expand

# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 100000000000;
const double PI = acos(-1);
 
struct edge { LL from, to, cost; };
edge es[2010];
 
LL d[2010];
bool negative[2010];
int v, e;
LL shortest_path(int s) {
	for (int i = 0; i < v; i++)d[i] = INF;
	d[s] = 0;
	for (int loop = 0; loop < v; loop++) {
		for (int i = 0; i < e; i++) {
			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;
			}
		}
	}
	return d[v];
}
int main() {
	cin >> v >> e;
	LL a[2010], b[2010], c[2010];
	for (int i = 0; i < e; i++) {
		cin >> a[i] >> b[i] >> c[i];
		c[i] = -c[i];
		es[i] = { a[i],b[i],c[i] };
	}
	LL ans = shortest_path(1);
	for (int loop = 0; loop < v; loop++) {
		for (int i = 0; i < e; i++) {
			if (d[a[i]] == INF) continue;
 
			if (d[b[i]] > d[a[i]] + c[i]) {
				d[b[i]] = d[a[i]] + c[i];
				negative[b[i]] = true;
 
			}
 
			if (negative[a[i]] == true) {
				negative[b[i]] = true;
 
			}
 
		}
 
 
	}
	if (negative[v]) {
		cout << "inf" << endl;
	}
	else {
		cout << -ans << endl;
	}
}

Submission Info

Judge Result