[BOJ] 1865 웜홀

문제: https://www.acmicpc.net/problem/1865

 

 

소스 코드:

#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <deque>
#include <string.h>
#include <algorithm>
#define inf 987654321
using namespace std;

typedef pair<int, int> P;
vector<vector<P>> adj;
int tc, n, m, wf, dist[501];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		cin >> n >> m >> wf;
		bool chk = false;
		adj.clear();
		adj.resize(n + 2);
		fill(dist, dist + n + 1, inf);
		dist[1] = 0;
		int q, w, e;
		for (int i = 0; i < m; i++) {
			cin >> q >> w >> e;
			adj[q].push_back({ e,w });
			adj[w].push_back({ e,q });
		}
		for (int i = 0; i < wf; i++) {
			cin >> q >> w >> e;
			adj[q].push_back({ -e,w });
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (auto& next : adj[j]) {
					if (dist[next.second] > dist[j] + next.first) {
						dist[next.second] = dist[j] + next.first;
						if (i == n) chk = true;
					}
				}
			}
		}
		if (chk) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}