POJ-3259-Wormholes
链接：https://vjudge.net/problem/POJ-3259
题意：
农夫有N（1-500）个农场，有M（1-2500）条无向的路，和W（1-200）个有向的虫洞。
给N,M,W。
在给出M条路径个走过的时间，W个有向虫洞和虫洞可以穿越回之前多久。
求能不能在某一时刻穿越回去看到自己。
思路：
bellman-ford算法，无向路为正权，有向虫洞为负权，当可以产生负权回环时，即可以实现穿越回去看到自己。
代码：
#include <iostream>
#include <memory.h>
using namespace std;
const int MAXN = 6000;
int n,m,w;
int b = 1;
struct Node
{
int l,r;
int v;
}node[MAXN];
int dis[510];
bool bellman_ford()
{
for (int i = 1;i<=n;i++)
dis[i] = 999999;
dis[1] = 0;
for (int i = 1;i <= n-1;i++)
{
bool flag = false;
for (int j = 1;j<b;j++)
{
int l = node[j].l,r = node[j].r,v = node[j].v;
if (dis[r] > dis[l] + v)
{
dis[r] = dis[l] + v;
flag = true;
}
}
if (!flag)
break;
}
for (int i = 1;i<b;i++)
if (dis[node[i].r] > dis[node[i].l] + node[i].v)
return true;
return false;
}
int main()
{
int t;
int l,r,v;
scanf("%d",&t);
while (t--)
{
scanf("%d%d%d",&n,&m,&w);
b = 1;
for (int i = 0;i<m;i++)
{
scanf("%d%d%d",&l,&r,&v);
node[b].l = l;
node[b].r = r;
node[b++].v = v;
node[b].l = r;
node[b].r = l;
node[b++].v = v;
}
for (int i = 0;i<w;i++)
{
scanf("%d%d%d",&l,&r,&v);
node[b].l = l;
node[b].r = r;
node[b++].v = -v;
}
if (bellman_ford())
printf("YES
");
else
printf("NO
");
}
return 0;
}