[C++] 백준 1865 웜홀

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
 
int TC = 0;
int N = 0;
int M = 0;
int W = 0;
int S = 0;
int E = 0;
int T = 0;
 
bool BellmanFord(int iStart, std::vector<std::tuple<int, int, int>> vec)
{
	std::vector<int> visit(N + 1, 25000001);
 
	visit[1] = 0;
 
	for (int i = 1; i < N; ++i) 
	{
		for (int j = 0; j < vec.size(); ++j)
		{	
			int iX = std::get<0>(vec[j]);
			int iY = std::get<1>(vec[j]);
			int iZ = std::get<2>(vec[j]);
 
			if (visit[iY] > visit[iX] + iZ)
			{
				visit[iY] = visit[iX] + iZ;
			}
		}
	}
 
	for (int i = 0; i < vec.size(); ++i)
	{
		int iX = std::get<0>(vec[i]);
		int iY = std::get<1>(vec[i]);
		int iZ = std::get<2>(vec[i]);
 
		if (visit[iY] > visit[iX] + iZ)
		{
			return true;
		}
	}
 
	return false;
}
 
int main() 
{
	std::cin >> TC;
 
	for (int i = 0; i < TC; ++i)
	{
		std::vector<std::tuple<int, int, int>> vec = {};
 
		std::cin >> N >> M >> W;
 
		for (int i = 0; i < M; ++i)
		{
			std::cin >> S >> E >> T;
 
			vec.push_back({ S, E, T });
			vec.push_back({ E, S, T });
		}
 
		for (int i = 0; i < W; ++i)
		{
			std::cin >> S >> E >> T;
 
			vec.push_back({ S, E, -T });
		}
 
		if (BellmanFord(N, vec))
		{
			std::cout << "YES\n";
		}
 
		else
		{
			std::cout << "NO\n";
		}
	}
 
	return 0;
}

벨만포드 알고리즘을 사용했습니다.

어떠 한 점에서 거리값을 구하기 위해서라면

음의 가중치가 없는 값을 찾을 경우에는 다익스트라자 알고리즘을 사용,

음의 가중치가 있을 경우 벨만포드 알고리즘을 사용하는 것이 좋습니다.

처음에는 제일 최소 거리의 값을 구합니다.

여기서 N-1회를 하는 이유는 1->N까지 한 길만 있을 경우 가 N-1이기 때문입니다. (최대횟수)

각 길마다 최소의 값을 구한 이후 제일 중요한 것은 음의 사이클입니다.

한 사이클을 돌았을 때 음수가 나왔을 경우, -가 나올 수 있다고 생각하기 때문에 어떠한 길을 계산했을 때,

-가 된다면 찾았다고 판단하고 YES를 입력합니다.

 

벨만 포드는 더 풀어봐야한다고 생각합니다.