BOJ : 1865 웜홀

---

[BOJ 1865(G4)리뷰]

벨만포드 알고리즘을 이용하는 문제다.

시간이 되돌아 가는것 = 음의 가중치를 갖는 간선이라고 생각하면 된다.
도로는 양방향으로 이동이 가능하므로 양방향으로 입력을 받고, 웜홀은 단방향이므로 단방향으로 입력을 받는다.

그 후에 벨만포드 알고리즘을 수행하며 사이클이 있는지 확인하여 결과를 출력하면 된다.

나는 이 문제에서 두가지 실수를 했다.

첫째는 MAX값을 INT_MAX값으로 설정하여 거리를 갱신하는 부분에 오버플로우가 나 올바른 결과가 나오지 않았다.

둘째는 방문했던 적이 있던 정점에 대해서만 거리를 갱신하는 작업을 수행했었는데, 만약 시작노드가 다른 노드와 연결되어 있지 않은 노드라면, 나머지 노드는 거리를 갱신할 수 없게된다. 따라서 이 조건을 없애야 한다.

위 두가지 오류를 잡고 정답처리를 받았다.

/*
	21.02.03
	BOJ : 1865 웜홀 (https://www.acmicpc.net/problem/1865)
	벨만포드 알고리즘
*/
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int,int>
#define MAX 1000000000
int tc;
int n, m, w;

vector <pii> adj[505];
int dist[505];

void init() {
	for (int i = 1; i <= n; i++) {
		dist[i] = MAX;
	}
}

void clear() {
	for (int i = 1; i <= n; i++) {
		adj[i].clear();
	}
}

bool bellman() {

	dist[1] = 0;
	for (int i = 1; i <= n; i++) {
		for (int cur = 1; cur <= n; cur++) {
			for (int j = 0; j < adj[cur].size(); j++) {
				auto nxt = adj[cur][j];

				int nDist = dist[cur] + nxt.second;
				if (dist[nxt.first] > nDist) {
					dist[nxt.first] = nDist;
					if (i == n) return true;
				}
			}
		}
	}

	return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> tc;

	while (tc--) {
		cin >> n >> m >> w;
		init();

		for (int i = 0; i < m; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			adj[a].push_back({ b,c });
			adj[b].push_back({ a,c });
		}

		for (int i = 0; i < w; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			adj[a].push_back({ b,-c });
		}

		bool isCycle = bellman();
		
		cout << (isCycle ? "YES\n" : "NO\n");
		
		clear();
	}
	
	
	return 0;
}