题目链接：http://poj.org/problem?id=3259
题意是有n个点，m条边，k个虫洞(权值为负)，输入完m条无向边后输入k条有向边，问能不能找到一个点，从这个点出发，最后回到这个点的时候权值是负的(时光倒流)。
首先这个可以用Floyd去跑一遍，然后遍历每个点看看有没有能得到负权的点，想看Floyd做法的可以看看这篇博客：POJ 3259 Wormholes(Floyd判负环)，这篇博客是用spfa去跑的，从一个点出发，我们只需要看在这个图中有没有负环存在(就是一个环的权值和为负的)，如果有的话，我们就可以以这个负环中的任意一点为起点，最终回来的时候就可以得到负的权值了。
AC代码：
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #define maxn 505 #define inf 0x3f3f3f3f using namespace std; struct Node{ int to,w,next; bool operator < (const Node &a) const{ return a.w < w; } }Edge[maxn * maxn]; int head[maxn * maxn],num; int dist[maxn]; bool vis[maxn]; int T,n,m,k; void init(){ memset(head,-1,sizeof(head)); num = 0; } void add(int u,int v,int w){ Edge[num].w = w; Edge[num].to = v; Edge[num].next = head[u]; head[u] = num ++; } bool spfa(){ int cnt[maxn]; memset(cnt,0,sizeof(cnt)); memset(dist,inf,sizeof(dist)); memset(vis,false,sizeof(vis)); dist[1] = 0; cnt[1] = 1; queue<int> q; q.push(1); while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = false; for(int i=head[u];i!=-1;i=Edge[i].next){ int v = Edge[i].to; if(dist[v] > dist[u] + Edge[i].w){ dist[v] = dist[u] + Edge[i].w; if(vis[v] == false){ cnt[v]++; q.push(v); vis[v] = true; if(cnt[v] >= n){ return true; } } } } } return false; } int main() { scanf("%d",&T); while(T--){ init(); scanf("%d%d%d",&n,&m,&k); for(int i=0;i<m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u, v, w); add(v, u, w); } for(int i=0;i<k;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u, v, -w); } if(spfa()){ puts("YES"); } else{ puts("NO"); } } return 0; }
