[백준/BOJ] 백준 1865번 : 웜홀

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

1865번: 웜홀

웜홀로 인해 간선 가중치가 음수인 것이 있으므로 start 정점에서부터 각 정점에 최단 경로를 구하는 벨만-포드 알고리즘을 사용하였고, 여기서 음수 사이클이 존재하는지 확인하였다. 왜냐하면 음수 사이클이 존재한다면 어떤 지점에서 출발하여 시간여행을 하고 다시 원래 지점으로 돌아왔을 때 과거로 가는 경우가 있기 때문이다

 

코드

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

int n, m, w;
vector<pair<int, int>> adj[500]; //걸리는 시간, 정점 순으로 저장한다

//그래프를 초기화 한다
void clear_adj()
{
	for (int i = 0; i < 500; i++)
		adj[i].clear();
}

//start정점에서 부터 각 정점에 최단 경로를 구하는 벨만-포드 알고리즘을 사용하였다(간선 가중치에 음수가 있으므로 벨만-포드 알고리즘을 사용하였다)
//그리고 여기서 음수 사이클이 존재하는지 확인하였다
bool Solve(int start)
{
	//start정점에서 부터 각 정점에 최단 경로를 저장한다
	//처음에는 매우 큰 수로 초기화 해놓는다
	vector<int> result(n, 987654321);

	//시작 지점으로 가는 최단 경로는 0이다
	result[start] = 0;

	//더 가까운 경로로 바뀐게 있는지 확인
	bool update;

	//한 지점에서 시간 여행을 하고 다시 돌아왔을때 시간이 과거로 가는 경우가 있는지 확인 
	bool ret = false;

	//n번 반복하는데 n번째에도 더 가까운 경로로 바뀌는것이 있으면
	//이것은 음수 사이클이 존재하는것이다
	for (int i = 0; i < n; i++)
	{
		update = false;
		for (int here = 0; here < n; here++)
		{
			for (int here_there = 0; here_there < adj[here].size(); here_there++)
			{
				int there = adj[here][here_there].second;
				int there_cost = adj[here][here_there].first + result[here];

				//더 가까운 경로로 바뀌는것이 있을때
				if (result[there] > there_cost)
				{
					result[there] = there_cost;
					update = true;
				}
			}
		}

		//더 가까운 경로로 바뀌는것이 없다면 음수 사이클이 없는것이다
		if (update == false)
			break;

		//n번째에도 더 가까운경로로 바뀌는것이 있다면 음수 사이클이 있는것이다
		if (i == n - 1 && update == true)
			ret = true;
	}

	return ret;
}

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

	int tc;
	int s, e, t;

	cin >> tc;

	for (int test = 0; test < tc; test++)
	{
		clear_adj();

		cin >> n >> m >> w;

		//정점들 사이 도로를 연결한다
		for (int i = 0; i < m; i++)
		{
			cin >> s >> e >> t;
			adj[s-1].push_back(make_pair(t, e-1));
			adj[e-1].push_back(make_pair(t, s-1));
		}

		//정점들 사이 웜홀을 연결한다
		for (int i = 0; i < w; i++)
		{
			cin >> s >> e >> t;
			adj[s-1].push_back(make_pair(-t, e-1));
		}

		if (Solve(0))
			cout << "YES" << "\n";
		else
			cout << "NO" << "\n";
	}

	return 0;
}