http://poj.org/problem?id=3259
题意 ： 农夫约翰农场里发现了很多虫洞，他是个超级冒险迷，想利用虫洞回到过去，看再回来的时候能不能看到没有离开之前的自己，农场里有N块地，M条路连接着两块地，W个虫洞，连接两块地的路是双向的，而虫洞是单向的，去到虫洞之后时间会倒退T秒，如果能遇到离开之前的自己就输出YES，反之就是NO。
样例解释 ：
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
第一行中的2代表有两组测试数据，第一组测试数据中，3,3,1代表着有3块地，3条路，1个虫洞，下面三行代表着编号几到几的权值是几，最后一行代表的是通过虫洞去到目的地时间倒退了t秒
思路 ： 这个题因为去到虫洞时间会倒退，而走农场之间相连的路又会花掉时间，明显是判断有没有负环，只要有负环，他只要一直走就能回到过去，典型的Bellman-Ford做法，本题采用的是spfa做法。
#include <cstdio>
#include <cstring>
#include <queue>
#include<iostream>
using namespace std; const int maxn = ;
const int maxm = ;
const int oo = <<;
struct node
{
int u;
int v;
int w;
int next;
} edge[maxm];
int dis[maxn];
int cnt;
int N,M,T;
int head[maxn];
bool vis[maxn];
queue<int>qu;
int count[maxn];
void add(int u, int v, int w)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
} int spfa(int s)
{
memset(count,,sizeof(count));
for(int i = ; i <= N; i++)
{
dis[i] = oo;
vis[i] = false;
}
dis[s] = ;
qu.push(s);
vis[s] = true;
while(!qu.empty())
{
int u = qu.front();
qu.pop();
vis[u] = false;
for(int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].v;
if(dis[u]+edge[i].w < dis[v])
{
dis[v] = dis[u]+edge[i].w;
if(++count[v] > N) return ;
if(!vis[v])
{
vis[v] = true;
qu.push(v);
}
}
}
}
return ;
} void init()
{
cnt = ;
memset(head, -, sizeof(head));
} int main()
{
int n ;
scanf("%d",&n);
while(n--)
{
init();
scanf("%d %d %d",&N,&M,&T);
int u, v, w;
for(int i = ; i <= M; i++)
{
scanf("%d %d %d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
for(int i = ; i <= T ; i++)
{
cin>>u>>v>>w;
add(u,v,(-*w));
}
int flag = spfa();
if(flag == )
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return ;
}
Bellman-Ford算法及其改进---SPFA算法可以参照下边这个博客
http://hi.baidu.com/laozhonggu/item/30a3f90d81b01fc975cd3c28