【POJ No. 3259】虫洞 Wormholes

【POJ No. 3259】虫洞 Wormholes

POJ题目地址

【题意】

在探索许多农场时，约翰发现了一些令人惊奇的虫洞。虫洞是非常奇特的，因为它是一条单向路径，可以将人穿越到虫洞之前的某个时间！约翰想从某个地点开始，穿过一些路径和虫洞，并在他出发前的一段时间返回起点，也许他将能够见到自己。

【输入输出】

输入：

第1行是单个整数F （1≤F ≤5），表示农场的数量。

每个农场的第1行有3个整数N 、M 、W ，表示编号为1～N 的N （1≤N≤500）块田、M （1≤M ≤2500）条路径和W （1≤W ≤200）个虫洞。第2～M+1行，每行都包含3个数字S 、E 、T ，表示穿过S 与E 之间的路径（双向）需要T 秒。两块田都可能有多个路径。第M +2～M +W +1行，每行都包含3个数字S 、E 、T ，表示对从S 到E 的单向路径，旅行者将穿越T 秒。没有路径需要超过10 000秒的旅行时间，没有虫洞可以穿越超过10 000秒。

输出：

对于每个农场，如果约翰可以达到目标，则输出“YES”，否则输出“NO”。

【样例】

【思路分析】

对于农场1，约翰无法及时返回；对于农场2，约翰可以在1→2→3→1的周期内及时返回，在他离开前1秒返回他的起始位置。他可以从周期内的任何地方开始实现这一目标。

根据输入样例1，如下图所示，

约翰无法在他出发之前的时间返回

根据输入样例2，如下图所示。

约翰可以在1→2→3→1的周期内及时返回，在他离开前1秒返回他的起始位置。他可以从周期内的任何地方开始实现这一目标。因为存在一个负环（边权之和为负）1→2→3→1，边权之和为-1。

【算法设计】

这道题其实就是判断是否有负环，使用SPFA判断负环即可。

普通道路是双向的，虫洞是单向的，而且时间为负值。

【算法实现】

#include<iostream>
#include<cstring>
#include<queue>using namespace std;
const int maxn = 510, maxe = 100001;const int inf = 0x3f3f3f3f;
int T, n , m , w, cnt;int head[maxn] , dis[maxn] , sum[maxn];
bool vis[maxn]; //标记是否在队列中struct node{int to , next , c;
}e[maxe];void add(int u , int v , int c){e[cnt].to = v;e[cnt].next = head[u];e[cnt].c = c;head[u] = cnt++;
}bool spfa(int u){queue<int>q;memset(vis , 0 , sizeof(vis));memset(sum , 0 , sizeof(sum));vis[u] = 1;dis[u] = 0;sum[u] ++;q.push(u);while(!q.empty()){int x = q.front();q.pop();vis[x] = 0;for(int i = head[x] ; ~i ; i = e[i].next){if(dis[e[i].to] > dis[x] + e[i].c){dis[e[i].to] = dis[x] + e[i].c;if(!vis[e[i].to]){if(++sum[e[i].to] >= n){return false;}vis[e[i].to] = 1;q.push(e[i].to);}}}} return true;
}bool solve(){memset(dis , 0x3f, sizeof(dis));for(int i = 1; i <= n ; i++){if(dis[i] == inf){ //如果已经达到该点且没有找到负环, 则不需要再从该点找 if(!spfa(i)){return 1;}}}return 0;
}int main(){cin >> T;while(T--){cnt = 0; cin >> n >> m >> w;memset(head , -1 , sizeof(head));int u , v, t;for(int i = 1; i <= m ; i++){cin >> u >> v >> t;add(u , v , t); //两条边 add(v , u , t);}for(int i = 1; i <= w; i ++){cin >> u >> v >> t;add(u , v , -t); //一条边 }if(solve()){cout << "YES" << endl;}else{cout << "NO" << endl;}}return 0;
}