问题的链接在这里。

很显然本题是要检测负权回路（沿着一条路径回到初始点，所需要的耗费为负值。）
首先在这里介绍一下bellman-ford算法和改进后的spfa算法。

1.bellman-ford算法

bellman-ford也是一种可以求单元最短路径的算法，与Dijkstra算法不同的是，它可以用来判断负权边是否存在。

松弛函数

首先来介绍一下松弛函数是什么。松弛函数虽然听起来很高大上，但实际上学过一点数据结构很快就明白它是什么东西了，设源点到点v的路径权值为s[v]，若存在u是边集的一个元素，边u到v的权值w(u,v)，使得s[u]+w(u,v)＜s[v]，那么就吧s[v]的权值更新为s[u]+w(u,v)，这就相当于松弛了一下，这就是松弛函数。

松弛函数执行的次数

现在视对边集E中的每一条边做一次松弛为一次迭代，考虑需要进行迭代的次数。显然，每一次迭代边的遍历顺序非常重要。如果每次松弛都能使得一个顶点的s值变小，那么很快我们就能获得这个源顶点的单源最短路径；如果每次遍历只能使一个顶点成功松弛（一次遍历至少要松弛一个顶点，除非单源最短路径已经求得），那么就需要进行N次迭代。（N是顶点的个数）所以最好的情况下需要进行1次迭代，最差情况下需要进行N-1次迭代。

bellman-ford算法

bellman-ford算法就是使用到了上面的松弛函数，通过不断地迭代，直到找到单源最短路径。能感觉得到bellmanford算法和dijkstra算法有点相似，都是不断地保证一个节点到源点的路径最短，从而最终获取单源最短路径。不同的地方是，松弛函数并不知道在一次松弛中哪个节点被确定了，只知道一定确定了至少一个节点，而dijkstra是确定了哪个点被确定，因为这个方面的不同，决定了dijkstra是典型的贪心算法，这种贪心策略也决定了它不能处理带负权的图，而bellman-ford算法是可以处理负权的。此外，dijkstra比较适合处理稀疏图，也就是边相对来说不是很密的图，而bellman-ford求解边比较多的图是比较快的。

bellman-ford算法能否确定负权回路呢？答案是肯定的，这也是bellman-ford的另一个优点。

算法的实现：因为每次肯定至少能松弛一条边，所以外层循环进行V-1次（如果一次迭代没有能够使得任何一条边松弛，那么循环退出；此外，如果存在负权环，算法也不会一直运行下去，因为至多运行V-1次。）；每次要遍历一遍边集，所以内层循环进行E次，因此它的最坏时间复杂度是O（VE）。每个内存循环都进行一次松弛操作，在循环执行完成后，再执行一次循环判断，如果这时还能有边被松弛，那么就一定存在负权回路。

具体的实现过程略过，网上一搜一大把，定义好数据结构就问题不大。

2.SPFA算法

首先来介绍一下SPFA的原理。在bellmanf-ford算法中，可不可以省略其中一部分不必要的松弛操作呢？再考虑一下松弛操作：

设源点到点v的路径权值为s[v]，若存在u是边集的一个元素，边u到v的权值w(u,v)，使得s[u]+w(u,v)＜s[v]，那么就吧s[v]的权值更新为s[u]+w(u,v)，这就相当于松弛了一下，这就是松弛函数。

节点u能够被松弛，一定是因为有个和它相邻的被松弛过的点v，才能使得s[u]+w(u,v)＜s[v]，从而进行松弛。因为，松弛操作一定发生源点到该店最短路径中松弛过的节点上，所以可以用一个数据结构来记录松弛过的点，这样可以避免冗余计算。这里常用的数据结构是队列，也可以改进为某种优先队列，譬如距离最小者优先的队列或者距离最大者优先的队列，我这里就使用普通的先进先出队列操作了。

使用SPFA算法后，循环的方式从外内循环了变成了循环检测队列是否为空，那么如何检测负权环呢？这就要用到刚刚我们记录节点的数据结构了，类似地，如果一个节点能够进入队列N次，那么说明是存在负权环了，可以通过这个机制来检测负权环。

算法的实现过程：首先将一个点加入队列中，然后进行循环，若队列不空则循环：出队一个元素，对它的所有邻居进行松弛，如果某一个节点被松弛成功，那么就把它加入队列中，同时该点的入队次数+1；然后判断进入队列的次数是否大于等于N，如果N就表明有负权回路，退出循环。

时间复杂度：本质仍然是bellman-ford算法，最坏的情况下时间复杂度仍然是O（VE）。

3.该题的具体实现

我这里使用了spfa算法，要注意的是spfa算法求得的是单源最短路径，所以我这里进行了循环，每个点使用了一次spfa算法判断是否有负权环。

该题的具体代码实现如下，各种可以修改我这里使用的数据结构，看看耗费的时间如何变化：

#include<iostream>
#include<queue>
using namespace std;
#define MAX 510
#define inf 0x3f3f3f3f
//**************************************************
//将该问题看作是求原点到原点的无回路最短路径
//可以采用求单源最短路径是SPFA算法和bellmanford算法
//这里采用SPFA算法 
//一般的SPFA算法是要避免负权回路的，但是本题如果存在负权回路，可以直接判定存在
//**************************************************
int N, W, M;
int times[MAX];
int dist[MAX];
int weight[MAX][MAX];
queue<int> q;
bool existNegativeLoop(int i) {
	if (times[i] != 0)return false;
	memset(times, 0, sizeof(times));
	times[i] = 1;
	dist[i] = 0;
	q.push(i);
	int current;
	while (!q.empty()) {
		current = q.front();
		q.pop();
		for (int j = 1; j <= N; j++) {
			if (dist[j] > dist[current] + weight[current][j]) {
				dist[j] = dist[current] + weight[current][j];
				q.push(j);
				times[j]++;
				if (times[j] >= N) return true;
			}
		}
	}
	return false;
}
int main() {
	int F;
	cin >> F;
	int i;
	int start, end, cost;
	while (F--) {
		cin >> N >> W >> M;
		memset(times, 0, sizeof(times));
		memset(weight, inf, sizeof(weight));
		//memset(dist, inf, sizeof(dist));
		//双向的道路
		for (i = 0; i < W; i++) {
			cin >> start >> end >> cost;
			if (cost < weight[start][end]) {
				weight[start][end] = weight[end][start] = cost;
			}
		}
		//单向的虫洞
		for (i = 0; i < M; i++) {
			cin >> start >> end >> cost;
			if (-cost < weight[start][end]) {
				weight[start][end]= -cost;
			}
		}
		//循环检测每个点是否有负权循环 一旦有一个就退出
		bool flag = false;
		for (i = 1; i <= N; i++) {
			memset(dist, inf, (N+1)*sizeof(int));
			if (existNegativeLoop(i)) { flag = true; break; }
		}
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;

	}
	return 0;
}