Submission #1609044

---

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;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 100000000000000;
const double PI = acos(-1);

bool negative[2010];
struct edge { LL from, to, cost; };
edge es[100000];

LL d[100000];
int V, E;
bool shortest_path(int s, int t) { // t: destination
	for (int i = 0; i <= V+1;i++) d[i] = INF;
	d[s] = 0;
	for (int i = 0; i < 2 * V;i++) {
		for (int j = 0; j < E;j++ ) {
			edge e = es[j];
			if (d[e.from] != INF && d[e.to]>d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;

				if (i >= V - 1 && e.to == t) return true;
			}
		}
	}
	return false;
}
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] };
	}
	if (shortest_path(1, V)) {
		cout << "inf" << endl;
	}
	else {
		cout << -d[V] << endl;
	}
}

Submission Info

Judge Result