CSES - Shared codeLink to this code:
https://cses.fi/paste/cfd81e7f5b4db001e2466/
#include <bits/stdc++.h>
#define db(x) cout<<x<<" "
#define db1(x) cout<<x<<'\n'
#define db2(x,y) cout<<x<<" "<<y<<'\n'
#define db3(x,y,z) cout<<x<<" "<<y<<" "<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define pair(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define ll long long int
#define all(a) a.begin(), a.end()
#define MAX_N 1e5
using namespace std;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
char dir[4] = {'R', 'L', 'D', 'U'};
bool check= false;
vector<bool>visit(2501, false);
class Edge {
public :
int src;
int dest;
int weight;
};
class Graph{
public :
int v;
int e;
Edge *edge;
Graph (int v, int e) {
this ->v = v;
this ->e = e;
edge = new Edge[e];
}
void addEdge (int u, int v, int w, int count) {
edge[count].src = u;
edge[count].dest = v;
edge[count].weight = w;
}
bool BellmanFord (int src) {
ll distance[v];
ll parent[v];
memset(parent, -1, sizeof(parent));
ll x;
for (int i=0; i<v; i++) {
if (i==src) {
distance[i] = 0;
}
else {
distance[i] = LLONG_MAX;
}
}
//Relaxation Code
for (int i = 1; i<=v; i++) {
x = -1;
for (int j=0; j<e; j++) {
int source = edge[j].src;
int destnation = edge[j].dest;
int wt = edge[j].weight;
//visit[source] = true;
if (distance[source]!=LLONG_MAX && distance[destnation]>distance[source] + wt) {
visit[source] = true;
distance[destnation] = distance[source] + wt;
parent[destnation] = source;
x = destnation;
}
}
}
if(x==-1)
return false;
check = true;
db1("YES");
rep(i,v)
x = parent[x];
vector<ll>cycle;
ll sex = x;
while(1) {
cycle.push_back(sex);
if(sex==x && cycle.size()>1)
break;
sex = parent[sex];
}
reverse(all(cycle));
rep(i, cycle.size()) {
db(cycle[i]+1);
}
return true;
}
};
void solve(){
ll n,m;
cin>>n>>m;
Graph g(n, m);
ll src=0;
vector<ll>source;
rep(i, m) {
ll u,v,w;
cin>>u>>v>>w;
u--;
v--;
g.addEdge(u,v,w,i);
source.push_back(u);
}
rep(i,source.size()) {
if(visit[source[i]] == false && g.BellmanFord(source[i])) {
return;
}
}
db1("NO");
}
int main(){
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}