#include <iostream>
using namespace std;


struct Edge {
	unsigned int start;
	unsigned int end;
	int weight;
};

int F, N, M, W, S, E, T, Edge_size;
int* d;
Edge* e;

inline void relax(Edge *e)
{
	if (d[e->start] + e->weight < d[e->end])
		d[e->end] = d[e->start] + e->weight;
}

bool bellman_ford()
{
	for (int i = 0; i < N; ++i)
		d[i] = 0;
	for (int i = 0; i < N - 1; ++i)
	{
		for (int j = 0; j < Edge_size; ++j)
			relax(&e[j]);
	}
	for (int i = 0; i < Edge_size; ++i)
	{
		if (d[e->start] + e->weight < d[e->end])
			return true;
	}
	return false;
}


int main()
{
	cin >> F;
	while (F--)
	{
		cin >> N >> M >> W;
		Edge_size = 2 * M + W;
		d = new int[N];
		e = new Edge[Edge_size];
		for (int i = 0; i < 2 * M; i = i + 2)
		{
			cin >> S >> E >> T;
			e[i].start = (--S);
			e[i].end = (--E);
			e[i].weight = T;
			e[i + 1].start = E;
			e[i + 1].end = S;
			e[i + 1].weight = T;
		}
		for (int i = 2 * M; i < Edge_size; ++i)
		{
			cin >> S >> E >> T;
			e[i].start = (--S);
			e[i].end = (--E);
			e[i].weight = -T;
		}
		if (bellman_ford())
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
		delete[] d;
		delete[] e;
	}
	
	return 0;
}

• 玩傻掉了。。好无聊的低级错误。。感谢USACO官方数据： (60) ULTMaster 2014-08-01 22:01:32