어흥

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

알고리즘/백준

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

라이언납시오 2020. 5. 6. 13:00
728x90
반응형

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

 

1865번: 웜홀

문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서

www.acmicpc.net

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;
}
728x90
반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준 3108] 로고 (C++)  (2) 2020.05.06
[백준 9370] 미확인 도착지 (C++)  (0) 2020.05.06
[백준 13334] 철로 (C++)  (0) 2020.05.06
[백준 1007] 벡터 매칭 (C++)  (2) 2020.05.05
[백준 1005] ACM Craft (C++)  (0) 2020.05.05
Comments