Referenced from here. // O( V + E ) #include <bits/stdc++.h> using namespace std; typedef pair< int, int > pii; typedef vector< pii > vp; typedef vector< int > vi; typedef vector< vi > vvi; int MAXV; int var_inv( int x ){ // 1 idx if( x <= MAXV ) return </bits/stdc++.h>…

Note that only negative cycles that are reachable from the source should exert their influence on the other nodes that could be reached from them. const ll LINF = 1LL << 60; void solve(){ int N, M; cin >> N >> M; vvp G( N ); for( int i = 0…