Need Help in "Need help in CSES problem "High Score" "

Hi, I was trying to solve High Score from the Graph Algorithms section of CSES. I tried using bellman ford for this problem but for some reason, my code is wrongly detecting the positive weight cycles in the graph , can anybody tell if there is something else that is needed to be taken care of or its some implementation error at my side?
@aryan12 @everule1

WA CODE :
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define ar array 
#define pb push_back 
#define vi vector
#define FOR(i,n) for(int i=0;i<n;i++)
const long mxN =1e5+2 ;
int n,m;
ll d[mxN],ans[mxN] ;
vector<ar<ll,2>>adj[mxN] ;
int main() {
  cin >> n >> m ;
  FOR(i,m){
    ll a,b,c;cin>> a >> b >> c ;
    adj[a].pb({c,b}) ;
  }
  memset(d,0xc0,sizeof(d)) ;
  d[1]=0 ;
  FOR(i,n){
    bool ok=0 ;
    for(int j=1;j<=n;j++)
      for(ar<ll,2> x:adj[j]){
        if(d[j]+x[0]>d[x[1]]){
          ok=1 ;
          d[x[1]]=d[j]+x[0] ;
        }
      }
    if(i==n-1&&ok){
        cout << -1 ;
        return 0;
    }
    ans[i]=d[n];
    
  }
  cout << ans[n-1]  ;
  
	return 0;
}


Bellman Ford algorithm is used to detect negative cycles.

And, I don’t understand your question…does it mean that your code can’t detect any cycle?

1 Like

Hard to say without the code itself.

1 Like

Sorry I forgot to attach the code, now its updated please check if possible

Yeah but we can manipulate it a little bit for determining positive cycles too.
I meant that my code is wrongly detecting the cycle even there is no cycle, it fails for 4 test cases and all of them have an answer which is not -1 but my code prints -1.

Perhaps the positive cycle is not connected to 1, and therefore unreachable. Maybe dfs from 1, and then ignore the unvisited nodes in the main part. Your code prints -1 in the existence of a positive a cycle, irrespective of whether it is reachable from 1.

3 Likes

yes, that makes alot of sense thanks for replying