[C++] 백준 1865 : 웜홀

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

1865번: 웜홀

백준 1865번 웜홀을 풀었다.

 

가중치가 음수인 간선이 존재하고 문제에서 음의 사이클이 존재하는지 묻고있다.

벨만 포드 알고리즘을 사용해서 문제를 풀었다.

 

1번 노드와 연결되어 있지 않아도 음의 사이클이 존재하면 그 사이클을 통해 시간을 되돌리는 여행을 할 수 있다.

2022.04.22 - [알고리즘/PS] - [C++] 백준 11657 : 타임머신

따라서 위의 글에서 사용한 dist[start] == INF 조건을 사용하지 않고 모든 노드를 확인해야 한다.

 

테스트케이스가 끝나면 항상 변수 초기화를 해줘야 한다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

#define INF 987654321

int tc, n, m, w;
vector<pair<pair<int, int>,int>> edge;
vector<long long> dist(501, INF);

int main() {
	cin >> tc;
	while (tc--) {
		cin >> n >> m >> w;
		int start, end, cost;
		bool yes = 0;
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &start, &end, &cost);
			edge.push_back({ {start,end},cost });
			edge.push_back({ { end,start }, cost });
		}
		for (int i = 0; i < w; i++) {
			scanf("%d %d %d", &start, &end, &cost);
			edge.push_back({ { start,end }, -cost });
		}

		dist[1] = 0;
		for (int i = 1; i <= n - 1; i++) {
			for (int j = 0; j < edge.size(); j++) {
				int start = edge[j].first.first;
				int end = edge[j].first.second;
				int cost = edge[j].second;
				long long next_cost = cost + dist[start];
				if (dist[end] > next_cost) {
					dist[end] = next_cost;
				}
			}
		}

		for (int i = 0; i < edge.size(); i++) {
			int start = edge[i].first.first;
			int end = edge[i].first.second;
			int cost = edge[i].second;
			long long next_cost = cost + dist[start];
			if (dist[end] > next_cost) {
				yes = 1;
			}
		}

		if (yes)
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';

		// init
		dist.assign(501, INF);
		edge.clear();
	}

	return 0;
}