백준 1865번 웜홀 C++

출처 : https://www.acmicpc.net/problem/1865

 

벨만-포드 알고리즘을 이용하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

const int INF = 987654321;

struct node {
	int s;
	int e;
	int t;
};

vector<node> nodes;

bool IsPossibleReduceTime(int n) {
	vector<int> dist(n + 1, INF);
	dist[1] = 0;

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < nodes.size(); j++) {
			int s = nodes[j].s;
			int e = nodes[j].e;
			int t = nodes[j].t;
			if (dist[e] > dist[s] + t) {
				dist[e] = dist[s] + t;
			}
		}
	}
	for (int j = 0; j < nodes.size(); j++) {
		int s = nodes[j].s;
		int e = nodes[j].e;
		int t = nodes[j].t;
		if (dist[e] > dist[s] + t) {
			return true;
		}
	}
	return false;
}

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

	int t;
	cin >> t;
	while (t--) {
		int n, m, w;
		cin >> n >> m >> w;
		for (int i = 0; i < m; i++) {
			int s, e, t;
			cin >> s >> e >> t;
			nodes.push_back({ s,e,t });
			nodes.push_back({ e,s,t });
		}
		for (int i = 0; i < w; i++) {
			int s, e, t;
			cin >> s >> e >> t;
			nodes.push_back({ s,e,-t });
		}
		bool res = IsPossibleReduceTime(n);
		if (res) cout << "YES";
		else cout << "NO";
		cout << "\n";
		nodes.clear();
	}

};