Submission #1281491

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define FOR(i, s, e) for (ll(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (ll(i) = (s); (i) > (e); (i)--)
#define debug(x) cout << #x << ": " << x << endl
#define mp make_pair
#define pb push_back
const ll MOD = 1000000007;
const ll INF = 1e9;
const ll LINF = 1e16;
const double PI = acos(-1.0);
ll dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
ll dy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/05/13  Problem: ABC 061 D / Link: http://abc061.contest.atcoder.jp/tasks/abc061_d  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----

強連結成分があればinf
でなければーでダイクストラ？

----解説ここまで---- */

ll N, M;
vector<pll>G[1010];
vector<pll>rG[1010];
ll ans = 0LL;
#define MAX 1100
bool used[MAX];
vector<ll >vs;
ll cmp[MAX];
void dfs(ll v) {
	used[v] = true;
	FOR(i, 0, (ll)G[v].size()) {
		if (used[G[v][i].first] == false)
			dfs(G[v][i].first);
	}
	vs.push_back(v);
}


void rdfs(ll v, ll k) {
	used[v] = true;
	cmp[v] = k;
	FOR(i, 0, (ll)rG[v].size()) {
		if (used[rG[v][i].first] == false)
			rdfs(rG[v][i].first, k);
	}
}


vector<ll> scc() {
	fill(used, used + MAX, false);
	vs.clear();
	FOR(i, 0, N) {
		if (!used[i])
			dfs(i);
	}
	fill(used, used + MAX, false);
	ll kx = 0;
	for (ll i = vs.size() - 1; i >= 0; i--) {
		if (!used[vs[i]])
			rdfs(vs[i], kx++);
	}
	vector<ll >xxxx;
	xxxx.push_back(kx);
	return xxxx;
}

ll d[MAX];
ll dijkstra() {
	FOR(i, 0, MAX)d[i] = -LINF;
	d[0] = 0;
	priority_queue<pll, vector<pll>>q;
	q.push(mp(0, 0));

	while (!q.empty()) {
		pll s = q.top(); q.pop();
		ll v = s.second; ll dis = s.first;
		if (dis < d[v])continue;
		FOR(i, 0, G[v].size()) {
			if (d[G[v][i].first] < G[v][i].second + d[v]) {
				d[G[v][i].first] = G[v][i].second + d[v];
				q.push(mp(d[G[v][i].first], G[v][i].first));
			}
		}
	}
		return d[N - 1];
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> N >> M;
	FOR(i, 0, M) {
		ll a, b, c; cin >> a >> b >> c;
		a--;
		b--;
		G[a].pb(mp(b, c));
		rG[b].pb(mp(a, c));
	}
	vector<ll >aaa = scc();
	if (aaa[0] != N) {
		cout << "inf" << endl;
		return 0;
	}

	ans = dijkstra();
	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result