P3385 【模板】负环

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2005, maxm = 3005;
 4 const int inf = 0x3f3f3f3f;
 5 struct edge {
 6     int v, w;
 7 };
 8 vector<edge> maps[maxn];
 9 int dis[maxn], n, m;
10 
11 bool BellmanFord(int s) {  // s为源点
12     fill(dis+1, dis+1+n, inf);
13     dis[s] = 0;
14     for (int i = 1; i <= n-1; i++) {
15         for (int u = 1; u <= n; u++) {
16             for (int j = 0; j < maps[u].size(); j++) {
17                 int v = maps[u][j].v;
18                 int w = maps[u][j].w;
19                 if (dis[u] + w < dis[v]) {
20                     dis[v] = dis[u] + w;
21                 }
22             }
23         }
24     }
25     
26     if (maps[s].size() == 0) return true;  // 如果s点没有和其他点相连，则没有负环 
27     for (int u = 1; u <= n; u++) {
28         for (int j = 0; j < maps[u].size(); j++) {
29             int v = maps[u][j].v;
30             int w = maps[u][j].w;
31             if (dis[u] + w < dis[v])
32                 return false;
33         }
34     }
35     return true;
36 }
37 int main() {
38     int t; scanf("%d",&t);
39     while (t--) {
40         scanf("%d%d",&n,&m);
41         for (int i = 1; i <= n; i++) maps[i].clear();
42 
43         for (int i = 1; i <= m; i++) {
44             int u, v, w; scanf("%d%d%d",&u,&v,&w);
45             if (w < 0) maps[u].push_back(edge{v,w});
46             else {
47                 maps[u].push_back(edge{v,w});
48                 maps[v].push_back(edge{u,w});
49             }
50         }
51         bool flag = BellmanFord(1);
52            if (flag) puts("N0");
53            else puts("YE5");
54     }
55 }