kuangbin专题专题四 Wormholes POJ

题目链接：https://vjudge.net/problem/POJ-3259

思路：求有无负环，起点随意选就可以，因为目的只是找出有没有负环，有了负环就可以让时间一直回退，那么一定能回到当初，这里我选择从1号点开始。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <string>
 6 #include <vector>
 7 using namespace std;
 8  
 9 typedef long long LL;
10 #define inf (1LL << 30) - 1
11 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
12 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
13 #define per(i,j,k) for(int i = (j); i >= (k); i--)
14 #define per__(i,j,k) for(int i = (j); i > (k); i--)
15 
16 const int N = 510;
17 int dis[N];
18 int n,m,t;
19 int u,v,w;
20 
21 struct node{
22     int u,v,w;
23 };
24 
25 vector<node> E;
26 
27 void init(){
28     memset(dis,inf,sizeof(dis));
29     E.clear();
30 }
31 
32 void input(){
33 
34     rep(i,1,m){
35 
36         cin >> u >> v >> w;
37         E.push_back(node{u,v,w});
38         E.push_back(node{v,u,w});
39     }
40 
41     rep(i,1,t){
42 
43         cin >> u >> v >> w;
44         E.push_back(node{u,v,-w});
45     }
46 }
47 
48 bool bellman_ford(){
49 
50     dis[1] = 0;
51     bool flag = true;
52     rep(i,2,n){
53 
54         flag = false;//判断一层循环中有没有出现可以更新的点
55         for(int o = 0; o < E.size(); o++){
56             if(dis[E[o].v] > dis[E[o].u] + E[o].w)
57                 dis[E[o].v] = dis[E[o].u] + E[o].w;
58 
59             flag = true;//还有可以更新的点
60         }
61 
62         if(!flag) break;//不存在可以更新的点了，直接退出
63     }
64     
65     //判断有无负环出现，即时间能不能减少
66     for(int o = 0; o < E.size(); o++){
67         if(dis[E[o].v] > dis[E[o].u] + E[o].w) return true;
68     }
69 
70     return false;
71 }
72 
73 int main(){
74  
75     ios::sync_with_stdio(false);
76     cin.tie(0);
77 
78     int T;
79     cin >> T;
80     while (T--){
81         cin >> n >> m >> t;
82         
83         init();
84         input();
85         if(bellman_ford()) cout << "YES" << endl;
86         else cout << "NO" << endl;
87     }
88 
89     getchar();getchar();
90     return 0;
91 }