💛III [백준 1865/C++] 웜홀

문제

BOJ 링크

풀이

시간여행을 시작해 다시 출발점으로 돌아왔을 때, 시간이 되돌아간 경우가 있는지 확인해야 한다.

시간을 간선이라고 생각했을 때, 시간 역행을 음의 가중치로 두고 음의 사이클이 존재하면 시간 여행을 할 수 있다.

간선의 가중치에 음수가 있으므로, 벨만 포드 알고리즘을 활용해 풀 수 있었다.

우선 모든 정점의 최소 비용을 알기 위해 반복문을 두 번 사용해 모든 간선을 확인한다.

간선을 모두 탐색한 이후, 그래프에 음의 사이클이 있는지 확인하기 위해 간선을 한 번 더 탐색한다. 만약 음의 사이클이 존재한다면, 최솟값이 다시 갱신되므로 true를 리턴한다.

코드

#include <iostream>
#include <vector>
using namespace std;

struct Edge
{
	int from, to, cost;
};

vector<Edge> graph;

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

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < graph.size(); j++)
		{
			int from = graph[j].from;
			int to = graph[j].to;
			int cost = graph[j].cost;

			if (dist[from] + cost < dist[to])
			{
				dist[to] = dist[from] + cost;
			}
		}
	}

	for (int i = 0; i < graph.size(); i++)
	{
		int from = graph[i].from;
		int to = graph[i].to;
		int cost = graph[i].cost;

		if (dist[to] > dist[from] + cost) return 1;
	}

	return 0;
}

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

	// test
	int test_case;
	cin >> test_case;

	for (int tc = 0; tc < test_case; tc++)
	{
		// input & init
		graph.clear();

		int n, m, w;
		cin >> n >> m >> w;

		for (int i = 0; i < m; i++)
		{
			int s, e, t;
			cin >> s >> e >> t;

			graph.push_back({ s, e, t });
			graph.push_back({ e, s, t });
		}

		for (int i = 0; i < w; i++)
		{
			int s, e, t;
			cin >> s >> e >> t;

			graph.push_back({ s, e, -t });
		}

		// solve
		if (bellmanFord(n)) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}

결과