本文主要是介绍POJ 3259 *** Wormholes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：农场主有f个农场，每个农场有n个田地，m条路，w个虫洞，走路从田地s到田地e需要花费t1时间，而每个虫洞可以从田地q到田地p，且使得时间倒流t2。求对于每个农场，农场主是否能从田地i出发，回到田地i的时间是在他出发的时间之前？
想法：其实就是判断田地之间是否存在负循环，用bellmanford算法就可以了，但是还是WA了两次。因为我忽略了这m条路事实上是可以往返的。
代码如下：
#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<cstring>
#include<sstream>
#include<set>
#include<string>
#include<iterator>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int INF = 0x3fffffff;struct Path {int u;int v;int value;
}path[5500];int dis[2000];bool bellman(int source,int n,int way) {for (int i = 0; i <= n; ++i)dis[i] = INF;dis[source] = 0;int flag = 1;for (int i = 0; i < n&&flag; ++i) {flag = 0;for (int j = 0; j < way; ++j)if (dis[path[j].v]>dis[path[j].u] + path[j].value) {dis[path[j].v] = dis[path[j].u] + path[j].value;flag = 1;}}return !flag;
}int main(void) {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);int f, n, m, w;cin >> f;while (f--) {cin >> n >> m >> w;int u, v, value;for (int i = 0; i < m; ++i) {cin >> u >> v >> value;path[i * 2].u = path[i * 2 + 1].v = u;path[i * 2].v = path[i * 2 + 1].u = v;path[i * 2].value = path[i * 2 + 1].value = value;//往返都需要添加}for (int i = 0; i < w; ++i) {cin >> path[2*m + i].u >> path[2*m + i].v >> path[2*m + i].value;path[2*m + i].value = -path[2*m + i].value;}bool flag = 1;for (int i = 0; i < n&&flag; ++i)flag = bellman(i + 1, n, 2*m + w);if (flag)cout << "NO" << endl;else cout << "YES" << endl;}return 0;
}这篇关于POJ 3259 *** Wormholes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
