[백준 C++] 1865 웜홀 - 벨만포드

1865번: 웜홀

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

const long long& Infinite = LLONG_MAX;

vector<vector<int>> EdgeList;
vector<long long> Solution;
queue<int> SearchQueue;

bool BellmanFord(int N, int K)
{
	for (int i = 0; i < N; ++i)
	{
		int EdgeSize = EdgeList.size();
		for (int j = 0; j < EdgeSize; ++j)
		{
			int Start = EdgeList[j][0];
			if (Solution[Start] != Infinite)
			{
				SearchQueue.push(j);
			}
		}

		while (!SearchQueue.empty())
		{
			int Current = SearchQueue.front();
			SearchQueue.pop();

			int Start = EdgeList[Current][0];
			int End = EdgeList[Current][1];
			int Weight = EdgeList[Current][2];

			long long NewWeight = Solution[Start] + Weight;
			if (NewWeight < Solution[End])
			{
				Solution[End] = NewWeight;
			}
		}
	}

	// Determine Infinite Cycle
	int EdgeSize = EdgeList.size();
	for (int j = 0; j < EdgeSize; ++j)
	{
		int Start = EdgeList[j][0];
		if (Solution[Start] != Infinite)
		{
			SearchQueue.push(j);
		}
	}

	while (!SearchQueue.empty())
	{
		int Current = SearchQueue.front();
		SearchQueue.pop();

		int Start = EdgeList[Current][0];
		int End = EdgeList[Current][1];
		int Weight = EdgeList[Current][2];

		long long NewWeight = Solution[Start] + Weight;
		if (NewWeight < Solution[End])
		{
			return true;
		}
	}

	return false;
}

void Test()
{
	int N, M, W;
	cin >> N >> M >> W;

	EdgeList.clear();
	EdgeList.reserve(2 * M + W);
	for (int i = 0; i < 2 * M + W; ++i)
	{
		EdgeList.emplace_back(vector<int>(3, 0));
	}

	for (int i = 0; i < M; ++i)
	{
		int Start, End, Weight;
		cin >> Start >> End >> Weight;

		EdgeList[i][0] = Start - 1;
		EdgeList[i][1] = End - 1;
		EdgeList[i][2] = Weight;

		EdgeList[M + i][0] = End - 1;
		EdgeList[M + i][1] = Start - 1;
		EdgeList[M + i][2] = Weight;
	}

	for (int i = 0; i < W; ++i)
	{
		int Start, End, Weight;
		cin >> Start >> End >> Weight;

		EdgeList[2 * M + i][0] = Start - 1;
		EdgeList[2 * M + i][1] = End - 1;
		EdgeList[2 * M + i][2] = -1 * Weight;
	}

	Solution.clear();
	Solution.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		Solution.emplace_back(0);
	}

	if (BellmanFord(N, 0))
	{
		cout << "YES\n";
	}
	else
	{
		cout << "NO\n";
	}
}

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

	int TC;
	cin >> TC;
	for (int i = 0; i < TC; ++i)
	{
		Test();
	}
}

---

벨만-포드 알고리즘을 사용해서 풀었습니다.

 

주의할 점은 서로 연결된 노드의 집합이 여러개 존재할 수 있다는 것입니다. (모든 노드가 연결되어있지 않을 수 있다.)

따라서 특정 한 가지 노드를 시작점으로 두지 말고

모든 노드에서 출발 가능하도록

최단 거리 배열을 Inf가 아닌 0으로 초기화를 해주어야 합니다.