POJ 3259 Wormholes 题解 《挑战程序设计竞赛》

POJ 3259 Wormholes

虫洞：农夫约翰有F个农场，每个农场有N块地，其间有M条路，W条时光隧道（时间倒流）。问是否可能回到过去？

2.5 它们其实都是“图”

最短路

依然很水很基础的 Bellman-Ford 判定负圈，什么都不用考虑，一个 Bellman-Ford 就结束了。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
using namespace std;

#define MAX_E (2500 + 200 + 16) * 2

// 从顶点from指向顶点to的权值为cost的边
struct edge
{
	int from, to, cost;
	edge(){}
	edge(int from, int to, int cost)
	{
		this->from = from;
		this->to = to;
		this->cost = cost;
	}
};

// 边
edge es[MAX_E];

// 最短距离
int d[MAX_E];
// V是顶点数，E是边数
int V, E;

// 是否存在负圈
bool find_negative_loop()
{
	memset(d, 0, sizeof(d));
	for (int i = 0; i < V; ++i)
	{
		for (int j = 0; j < E; ++j)
		{
			edge e = es[j];
			if (d[e.to] > d[e.from] + e.cost)
			{
				d[e.to] = d[e.from] + e.cost;
				// 如果更新了V次，则存在负圈
				if (i == V - 1)
				{
					return true;
				}
			}
		}
	}
	return false;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int F;
	cin >> F;
	while (F--)
	{
		int N, M, W;
		cin >> N >> M >> W;
		V = N;
		E = 0;
		for (int i = 0; i < M; ++i)
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			--from;
			--to;
			es[E].from = from;
			es[E].to = to;
			es[E].cost = cost;
			++E;
			// 无向图再来一次
  			es[E].from = to;
  			es[E].to = from;
  			es[E].cost = cost;
  			++E;
		}
		for (int i = 0; i < W; ++i)
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			--from;
			--to;
			es[E].from = from;
			es[E].to = to;
			es[E].cost = -cost;
			++E;
		}
		if (find_negative_loop())
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3259 Wormholes 题解 《挑战程序设计竞赛》