골드3 - 백준 1865 웜홀

백준 1865 웜홀

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

접근방법

이 문제는 결국 음수 사이클이 있는지 없는지 여부를 판단하는 문제였다. 음수 사이클을 확인하기 위해서 해당 노드에 몇번 방문하는지 체크해주었고, N번 이상 방문한다면 음수 사이클이 있는 것으로 확인했다.

풀이

다익스트라와 동일하게 우선순위 큐를 선언하여 visited배열에 최소거리로 노드들의 거리를 갱신해주었다. 그리고 visited_cnt 배열도 선언하여 해당 노드에 방문을 한 횟수를 기록해주었다. 만약 정상적으로 다익스트라가 끝나지 않는다면, visited_cnt 배열을 확인하여 N보다 크거나 같다면 반복문을 종료하고 음수 사이클이 있는 것으로 YES를 출력하였고, 정상적으로 종료된다면 NO를 출력하여주었다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
int visit_cnt[501];
int visited[501];

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

	int T;
	cin >> T;

	while (T--)
	{
		memset(visit_cnt, 0, sizeof(visit_cnt));
		int N, M, W;
		cin >> N >> M >> W;

		vector<vector<pair<int, int>>> route;
		for (int i = 0; i <= N; i++)
		{
			vector<pair<int, int>> temp;
			route.push_back(temp);
		}

		for (int i = 0; i < M; i++)
		{
			int a, b, c;
			cin >> a >> b >> c;

			route[a].push_back({ b, c });
			route[b].push_back({ a,c });
		}

		for (int i = 0; i < W; i++)
		{
			int a, b, c;
			cin >> a >> b >> c;

			route[a].push_back({ b, c * -1 });
		}

		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		memset(visited, -1, sizeof(visited));
		bool flag = false;

		for (int i = 1; i <= N; i++)
		{
			if (visit_cnt[i] != 0)
				continue;

			visit_cnt[i] = 1;
			visited[i] = 0;
			pq.push({0, i});
			while (!pq.empty())
			{
				int cur = pq.top().second;
				int cost = pq.top().first;
				pq.pop();

				if (visit_cnt[cur] > N)
				{
					flag = true;
					break;
				}
				for (int j = 0; j < route[cur].size(); j++)
				{
					if (visited[route[cur][j].first] == -1 || visited[route[cur][j].first] > route[cur][j].second + cost)
					{
						visited[route[cur][j].first] = route[cur][j].second + cost;
						visit_cnt[route[cur][j].first]++;
						pq.push({ visited[route[cur][j].first], route[cur][j].first});
					}
				}
			}

			if (flag)
				break;
		}

		if (flag)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}