CSES - Shared codeLink to this code:
https://cses.fi/paste/44db546d30a77b7863a4ba/
#include<bits/stdc++.h>
using namespace std;
#define nline '\n';
#define fastio ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(15);
typedef long long ll;
typedef long double ld;
const ll N = 2505;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e16;
int dx[] = { -1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
vector<pair<ll, ll>>g[N];
int n;
bool reachable(int node) {
queue<int>q;
q.push(node);
vector<int>vis(N);
vis[node] = 1;
while (q.size()) {
int par = q.front();
q.pop();
for (auto p : g[par]) {
int child = p.first;
if (!vis[child]) {
vis[child] = 1;
q.push(child);
}
}
}
return vis[n];
}
void solve() {
int m;
cin >> n >> m;
vector<vector<ll>>edges;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
edges.push_back({u, v, w});
}
vector<ll>dist(n + 1, -inf);
dist[1] = 0;
for (int i = 0; i < n - 1; i++) {
for (auto &v : edges) {
ll from = v[0], to = v[1], w = v[2];
if (dist[from] != -inf and dist[from] + w > dist[to]) dist[to] = dist[from] + w;
}
}
for (int i = 0; i < m; i++) {
ll u = edges[i][0], v = edges[i][1], w = edges[i][2];
if (dist[u] != -inf and dist[u] + w > dist[v] and reachable(v)) {
cout << -1;
return;
}
}
cout << dist[n];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
fastio;
int tc = 1;
// cin >> tc;
int t = tc;
while (tc--) {
//cout << "Case #" << t - tc << ": ";
solve();
cout << nline;
}
return 0;
}