Help with CSES High Score Problem

general
, ,
1

Link to the problem: CSES - High Score
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[1] = 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?

2

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.

5 Likes
3

Whats the intuition behind the logic of reversing the adjacency list is it any standard algo or something

4

just as he mentioned, graph may be directed and it may not be possible for that cycle to be included in any of the paths from 1 to n. So a cycle exists but should not affect our result. For checking if it does not do so, we can use that dfs idea described earlier.