 # Help with CSES High Score Problem

My Code:

``````#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
const ll INF = 1e18;

int main()
{
FASTIO
int n, m;
cin >> n >> m;
vector<tuple<int,int,int>> edges;
for(int i=0; i<m; i++)
{
int a, b, c;
cin >> a >> b >> c;
edges.push_back({a,b,-c});
}
ll dist[n+1];
for(int i=0; i<=n; i++) dist[i] = INF;
dist = 0;
bool flag = false;
for(int i=1; i<=n; i++)
{
for(auto e : edges)
{
if(dist[get<0>(e)] < INF)
{
if(dist[get<0>(e)] + (ll) get<2>(e) < dist[get<1>(e)])
{
dist[get<1>(e)] = dist[get<0>(e)] + (ll) get<2>(e);
if(i == n) flag = true;
}
}
}
}
if(flag) cout << "-1\n";
else cout << -dist[n] << "\n";

return 0;
}
``````

Test cases on which it fails:
It fails on a total of three test cases out of the 18 test cases, and one of them is given below

``````4 4
1 2 1
2 3 1
3 2 1
1 4 1

Correct Output: 1
My Output:  -1
``````

From the test case given above it is clear that the code did find a positive cycle (in terms of the original graph) and that cycle is reachable from the starting node. The only problem is that there is no way to reach back to the starting node from that cycle.

Can anybody help me solve this problem?

DFS on the reverse adjacency list from n, and find all visited vertices. Ignore all edges that contain a vertex that was not visited.
Also just use a `struct edge` with `int u,v,w`. Tuples are confusing to read.

2 Likes