Submission #2860470

---

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>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
# include <cstdlib>
# include <tuple>
# include <array>
# include <climits>
#define ll long long int
#define rep(i,rept) for (ll i = 0; i < rept; i++)
#define yes(b) std::cout<< (b ? "Yes" : "No")
#define YES(b) std::cout<< (b ? "YES" : "NO")
const ll INF = 1LL << 50;
using namespace std;
/*int ketawa(ll num) {
	int dig, sum = 0;
	while (num) {
		dig = num % 10;
		sum = sum + dig;
		num = num / 10;
	}
	return sum;
}
*/
bool keta(ll num, vector<int> v) {
	int dig;
	while (num) {
		dig = num % 10;
		for (auto& i : v) {
			if (dig == i) {
				return false;
			}
		}
		num = num / 10;
	}
	return true;
}

ll func(ll a, ll b, ll c, ll d,int n) {
	return ((c / (d - b) + n)*(d - b)) + (a % (d - b));
}
int main(void) {
	int N, M;
	cin >> N >> M;

	const int NMAX = 1000;
	const int MMAX = 2000;
	int a[MMAX], b[MMAX];
	ll c[MMAX];

	for (int i = 0; i < M; ++i) {
		cin >> a[i] >> b[i] >> c[i];
		c[i] = -c[i];

	}

	ll dist[NMAX];

	for (int i = 0; i < N; ++i) {
		dist[i] = INF;

	}

	dist[0] = 0;


	for (int loop = 0; loop < N - 1; ++loop) {
		for (int i = 0; i < M; ++i) {

			if (dist[a[i] - 1] == INF) continue;

			if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
				dist[b[i] - 1] = dist[a[i] - 1] + c[i];

			}

		}

	}

	ll ans = dist[N - 1];


	bool negative[NMAX];

	for (int i = 0; i < N; ++i) {
		negative[i] = false;

	}

	for (int loop = 0; loop < N; ++loop) {
		for (int i = 0; i < M; ++i) {
			if (dist[a[i] - 1] == INF) continue;

			if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
				dist[b[i] - 1] = dist[a[i] - 1] + c[i];
				negative[b[i] - 1] = true;

			}

			if (negative[a[i] - 1] == true) {
				negative[b[i] - 1] = true;

			}

		}

	}


	if (negative[N - 1])
		cout << "inf" << endl;
	else
		cout << -ans << endl;

	return 0;

}

Submission Info

Judge Result