Wormholes SPFA算法

题目链接：POJ-3259

农夫 FJ 有 N 块田地【编号 1…n】 (1<=N<=500)
田地间有 M 条路径 【双向】(1<= M <= 2500)
同时有 W 个孔洞,可以回到以前的一个时间点【单向】(1<= W <=200)
问：FJ 是否能在田地中遇到以前的自己

思路

田地间的双向路径加边,权值为正
孔洞间的单向路径加边,权值为负【可以回到以前】
判断有向图是否存在负环
因为如果存在了负数环,时间就会不停的减少,
那么 FJ 就可以回到以前更远的地方,肯定能遇到以前的自己的
运用Spfa算法，当某个点入队次数 >= 顶点数， 说明存在负权值回路，我们直接return true；否则dist数组里存储的就是单源最短路的距离；

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;#define MAX_N 550
#define MAX_M 5050
#define INF 0x3f3f3f3fint head[MAX_M], vis[MAX_N], dist[MAX_N], cnt = 0, Count[MAX_N];struct Node{int to, val, next;
}edge[MAX_M];void init(int n)
{cnt = 0;memset(Count, 0, sizeof(Count));memset(head, -1, sizeof(head));memset(vis, 0, sizeof(vis));for(int i = 1; i<=n; i++){dist[i] = INF;}
}void add(int x, int y, int val)
{edge[cnt].to = y;edge[cnt].val = val;edge[cnt].next = head[x];head[x] = cnt++;
}bool Spfa(int n, int v)
{queue<int> S;S.push(v);dist[v] = 0;vis[v] = 1;Count[v]++;while(!S.empty()){int k = S.front();S.pop();vis[k] = 0;for(int i = head[k]; i != -1; i = edge[i].next){int v = edge[i].to;if(dist[k] + edge[i].val < dist[v]){dist[v] = dist[k] + edge[i].val;if(!vis[v]){S.push(v);Count[v]++;vis[v] = 1;if(Count[v] >= n)return true;}}}}return false;
}int main()
{int T;cin >> T;while(T--){int n, a, b;cin >> n >> a >> b;init(n);for(int i = 1; i<=a; i++)//正权无向边{int x, y, val;cin >> x >> y >> val;add(x, y, val);add(y, x, val);}for(int i = 1; i<=b; i++){int x, y, val;cin >> x >> y >> val;add(x, y, -val);}if(Spfa(n, 1))cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}