P3385 【模板】负环

// Bellman-Ford算法 O(nm)
#include<bits/stdc++.h>
#define INF 0X3F3F3F3F
using namespace std;
const int N=1e4+5;
struct node {int v, w;
};
vector<node> e[N];
int t, n, m, d[N];
bool bellman(int s) {memset(d, INF, sizeof d); d[s]=0;bool flag; //是否松弛 for(int i=1; i <= n; i++) { //n轮 flag=false;for(int u=1; u <= n; u++) { //n点 if(d[u] == INF) continue;for(auto i : e[u]) { // u的出边 int v=i.v, w=i.w;if(d[v] > d[u]+w) {d[v]=d[u]+w;flag=true;} }}if(!flag) break;}return flag; //第n轮仍为true则有环 
}
signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> t;while(t--) {cin >> n >> m;for(int i=1; i <= n; i++) e[i].clear(); for(int i=1, u, v, w; i <= m; i++) {cin >> u >> v >> w;e[u].push_back({v, w});if(w >= 0) e[v].push_back({u, w});}if(bellman(1)) puts("YES");else puts("NO");}return 0;
}

// spfa算法 O(m~nm)
#include<bits/stdc++.h>
#define INF 0X3F3F3F3F
using namespace std;
const int N=1e4+5;
struct node {int v, w;
};
vector<node> e[N];
int t, n, m, d[N], vis[N], cnt[N];bool spfa(int s) {memset(d, INF, sizeof d); d[s]=0;memset(vis, false, sizeof vis);memset(cnt, 0, sizeof cnt); queue<int> q; q.push(s); vis[s]=true; //标记在队中 while(!q.empty()) {int u=q.front(); q.pop(); vis[u]=false; //标记不在队中 for(auto i : e[u]) {int v=i.v, w=i.w;if(d[v] > d[u]+w) {d[v]=d[u]+w;if(!vis[v]) //不在队中才入队 q.push(v), vis[v]=true; cnt[v]=cnt[u]+1; //边数+1 if(cnt[v] >= n) return true; //有负环 } }}return false; 
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> t;while(t--) {cin >> n >> m;for(int i=1; i <= n; i++) e[i].clear(); for(int i=1, u, v, w; i <= m; i++) {cin >> u >> v >> w;e[u].push_back({v, w});if(w >= 0) e[v].push_back({u, w});}if(spfa(1)) puts("YES");else puts("NO");}return 0;
}