代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int t , n , m , p , dis[N] , vis[N] , cnt[N];
struct node {
	int id , num;
} ;
vector <node> v[N];
queue <int> q;
void start () {
	for (int i = 1;i <= n;i ++) v[i].clear ();
	while (q.size() > 0) q.pop ();
	memset (dis , 0x3f , N );
	memset (vis , 0 , N );
	memset (cnt , 0 , N );
}
bool spfa (int s) {
	dis[s] = 0; vis[s] = 1;
	q.push ( s ) ;
	while (q.size() > 0) {
		int u = q.front(); q.pop ();
		vis[u] = 0;
		for (auto e : v[u]) {
			int id = e.id , num = e.num;
			if (dis[id] > dis[u] + num) {
				dis[id] = dis[u] + num;
				cnt[id] = cnt[u] + 1;
				if (cnt[id] >= n) return false;
				if ( !vis[id] ) q.push (id) , vis[id] = 1;
			}
		}
	}
	return true;
}
int main () {
	cin >> t;
	while (t --) {
		cin >> n >> m >> p;
		start ();
		while (m --) {
			int a , b , c; cin >> a >> b >> c;
			v[a].push_back ( node {b , c} );
			v[b].push_back ( node {a , c} );
		}
		while (p --) {
			int a , b , c; cin >> a >> b >> c;
			v[a].push_back ( node {b , -c} );
		}
		bool flag = spfa (1);
		if (flag == true) cout << "NO\n";
		if (flag == false) cout << "YES\n";
	}
	return 0;
}

提交记录