【POJ】3259 Wormholes

题意：n个农场，m条双向路径，w条单向路径（虫洞）。单向虫洞路径是负值。农夫想知道自己能不能看到自己（X）。

题解：其实刚开始没太读懂题意。然后其实如果他能看到自己，说明已经通过虫洞形成了一个负环。也就是通过spfa寻找负环（负权回路）。这里的判断就是加一个cnt[]数组记录该点的入队次数，大于等于n说明已经形成负环。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<stack>
 4 #include<vector>
 5 #include<queue>
 6 #include<algorithm>
 7 using namespace std;
 8 const int maxn = 2e5+7;
 9 const int inf = 0xffffff;
10 vector< pair<int,int> > e[maxn];
11 
12 int n,m,w;
13 int d[maxn],inq[maxn];
14 int cnt[maxn];
15 
16 void init(){
17     for(int i = 0; i <= n; i++)
18         e[i].clear();
19 }
20 
21 void spfa(){
22     for(int i = 0 ;i <= n ; i++)
23         inq[i] = 0,d[i] = inf,cnt[i] = 0;
24     queue<int>Q;
25     Q.push(1);
26     d[1] = 0;
27     inq[1] = 1;
28     cnt[1] = 1;
29     while( !Q.empty() ){
30         int u = Q.front();
31         Q.pop();
32         inq[u] = 0;
33         for(int i = 0; i < e[u].size() ; i++){
34             int v = e[u][i].first;
35             int val = e[u][i].second;
36             if(d[v] > d[u] + val){
37                 d[v] = d[u] + val;
38                 if(inq[v] == 0){
39                     cnt[v]++;
40                     inq[v] = 1;
41                     if(cnt[v] >= n){    //判定一点入队次数大于总顶点数，存在负环
42                         printf("YES
");
43                         return;
44                     }
45                     Q.push(v);
46                 }
47             }
48         }
49 
50     }
51     printf("NO
");
52 }
53 int main() {
54     int F;
55     cin>>F;
56     while(F--){
57         cin>>n>>m>>w;
58         init();
59         //双向正权
60         int x,y,z;
61         for(int i = 1; i <= m ;i++){
62             cin>>x>>y>>z;
63             e[x].push_back(make_pair(y,z));
64             e[y].push_back(make_pair(x,z));
65         }
66         //单向负权
67         for(int i = 1; i <= w; i++){
68             cin>>x>>y>>z;
69             e[x].push_back(make_pair(y,-z));
70         }
71         spfa();
72     }
73 
74     return 0;
75 }