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;
}