1865 ์›œํ™€

์ฝ”๋“œ

#include <bits/stdc++.h>
 
using namespace std;
 
int tc, N, M, W, road[501][501];
long long d[501];
bool check[501][501];
vector<int> connect[501];
 
bool belmanford();
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	cin >> tc;
 
	while (tc--) {
		cin >> N >> M >> W;
		int a, b, c;
 
		for (int i = 1; i <= N; i++) {
			d[i] = 2000000000000;
			connect[i].clear();
		}
		d[1] = 0;
		memset(check, 0, sizeof(check));
 
		for (int i = 0; i < M; i++) {
			cin >> a >> b >> c;
			connect[a].push_back(b);
			connect[b].push_back(a);
			if (check[a][b])
				road[a][b] = min(road[a][b], c);
			else
				road[a][b] = c;
			road[b][a] = road[a][b];
			check[a][b] = true;
			check[b][a] = true;
		}
		for (int i = 0; i < W; i++) {
			cin >> a >> b >> c;
			connect[a].push_back(b);
			road[a][b] = min(road[a][b], -c);
		}
		if (belmanford())
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}
 
bool belmanford() {
	for (int i = 0; i < N - 1; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k < connect[j].size(); k++)
				d[connect[j][k]] = min(d[connect[j][k]], d[j] + road[j][connect[j][k]]);
		}
	}
 
	for (int j = 1; j <= N; j++) {
		for (int k = 0; k < connect[j].size(); k++)
			if (d[connect[j][k]] > d[j] + road[j][connect[j][k]])
				return true;
	}
	return false;
}