[POJ]3259 Wormholes

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

这道题本质上就是找图中有没有负权环的问题，我们在这篇文章提过，用Bellmand-Ford和Floyd可以检测负权环，我们这里用Bellman Ford来做。Bellman-Ford的时间复杂度为O(V * E)。代码如下：

	//poj 3259
	/*
	While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
	As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
	To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.
	Input
	Line 1: A single integer, F. F farm descriptions follow.
	Line 1 of each farm: Three space-separated integers respectively: N, M, and W
	Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
	Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
	Output
	Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).
	*/
	#include <iostream>
	#include <cstring>
	using namespace std;
	const int MAXN = 505;
	const int MAXM = 2505;
	const int INF = 0x3f3f3f3f;
	int dist[MAXN];
	int F;
	int N, M, W;
	struct Edge
	{
	int from, to, weight;
	} edges[MAXM * 2 + 205];
	bool hasNegCycle()
	{
	//run bellman ford to find negative cycle
	//total N - 1 times, since the longest path in MST is at most N - 1
	//start at farm 1
	dist[1] = 0;
	for(int i = 1; i < N; ++i)
	{
	for(int j = 0; j < 2 * M + W; ++j)
	{
	int from = edges[j].from, to = edges[j].to, cost = edges[j].weight;
	if(dist[from] < dist[to] - cost)dist[to] = dist[from] + cost;
	}
	}
	//run one more time to detect negative cycle
	for(int j = 0; j < 2 * M + W; ++j)
	{
	int from = edges[j].from, to = edges[j].to, cost = edges[j].weight;
	if(dist[from] < dist[to] - cost)return true;
	}
	return false;
	}
	int main()
	{
	cin >> F;
	while(F--)
	{
	cin >> N >> M >> W;
	int s, e, t;
	int m = 0;
	//Farm
	for(int i = 0; i < M; i++)
	{
	cin >> s >> e >> t;
	//bidirectional path
	edges[m].from = s;
	edges[m].to = e;
	edges[m++].weight = t;
	edges[m].from = e;
	edges[m].to = s;
	edges[m++].weight = t;
	}
	//Worm hole
	for(int i = 0; i < W; i++)
	{
	cin >> s >> e >> t;
	//single direction
	edges[m].from = s;
	edges[m].to = e;
	edges[m++].weight = -t;
	}
	memset(dist, INF, sizeof(dist));
	if(hasNegCycle())
	cout << "YES" << endl;
	else
	cout << "NO" << endl;
	}
	return 0;
	}

view raw POJ_3259_Wormholes.cpp hosted with ❤ by GitHub