Submission #3597212

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

const ll INF = (1LL<<50);
const int MAX_N = 1e3+10;

struct Edge
{
	int to;
	ll cost;
	Edge(int to, ll cost) : to(to), cost(cost) {}
};

typedef vector<vector<Edge> > AdjList;
AdjList G(MAX_N);
int n;
vector<ll> dist;

bool bellman_ford(ll s){
	dist = vector<ll> (n, INF);
	dist[s] = 0;
	for (int i = 0; i < n; ++i) {
		for (int v = 0; v < n; ++v) {
			for (int k = 0; k < G[v].size(); ++k) {
				Edge e = G[v][k];
				if (dist[v] != INF && dist[e.to] > dist[v] + e.cost)
				{
					dist[e.to] = dist[v] + e.cost;
					if (i==n-1) return true;
				}
			}
		}
	}
	return false;
}


int main(int argc, char const *argv[])
{
	int m;
	cin >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		int a, b;
		ll c;
		cin >> a >> b >> c;
		a--;
		b--;
		c *= -1;
		G[a].push_back(Edge(b, c));
	}

	bool tf = bellman_ford(0);

	if (tf) cout << "inf" << endl;
	else {
		cout << -dist[n-1] << endl;
	}
	return 0;
}

Submission Info

Judge Result