[백준 1865] 웜홀 (C++)

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

1865번: 웜홀

1. 주의할 점

- 음의 가중치인 간선이 존재하기 때문에, 벨만포드 알고리즘을 사용한다

- 시작 Node가 정해져 있지 않아서 Dist[1] = 0, 나머지 Dist값은 전부 MAX로 초기 설정하고 시작하면 안된다 -> Dist 갱신할 때 Dist[next]!=MAX와 같은 조건도 없어야 한다

- 매 TC마다 V[]와 Dist[]를 초기화한다

 

2. 구현

- 도로의 경우 양방향, 웜홀을 단방향이며 가중치의 값을 음수로 V[]에 저장한다

- N-1번 동안 Dist를 갱신하고, N번째에도 Dist가 갱신된다면 음의 사이클이 존재한다고 판단하여 YES를 출력하고, 음의 사이클이 없다면 NO를 출력한다

 

#define MAX 9876543210
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct info {
	int idx;
	long long val;
};
info tmp;
vector<info> v[501];
long long dist[501];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, node, edge, warmhole, s, e;
	long long val;
	cin >> test;
	for (int t = 0; t < test; t++) {
		cin >> node >> edge >> warmhole;
		for (int i = 1; i <= node; i++) {
			v[i].clear();
			dist[i] = MAX;
		}
		for (int i = 0; i < edge; i++) {
			cin >> s >> e >> val;
			tmp.val = val;
			tmp.idx = e;
			v[s].push_back(tmp);
			tmp.idx = s;
			v[e].push_back(tmp);
		}
		for (int i = 0; i < warmhole; i++) {
			cin >> s >> e >> val;
			tmp.idx = e;
			tmp.val = -val;
			v[s].push_back(tmp);
		}
		bool cycle = false;
		for (int i = 1; i <= node; i++) {
			for (int j = 1; j <= node; j++) {
				int from = j;
				for (int k = 0; k < v[from].size(); k++) {
					int next = v[from][k].idx;
					int nv = v[from][k].val;
					if (dist[next] > dist[from] + nv) {
						dist[next] = dist[from] + nv;
						if (i == node) {
							cycle = true;
							break;
						}
					}
				}
				if (cycle) break;
			}
			if (cycle) break;
		}
		if (cycle) cout << "YES\n";
		else cout << "NO\n";
	}
	system("pause");
	return 0;
}