[C++]백준(BOJ) - 11657 타임머신(벨만-포드)

 

난이도 : 골III

알고리즘 유형 : 벨만-포드 알고리즘

풀이 방법 : n - 1(간선 최단 경로), edge 순회

 

문제 예시

• 입력
  • N개의 도시와 M개의 버스 노선 정보가 주어집니다.
  • 각 버스는 출발 도시, 도착 도시, 그리고 소요 시간이 주어집니다.
  • 시간 C가 음수일 경우에는 타임머신처럼 시간을 되돌리는 효과가 있으므로,
    이로 인한 무한 루프를 감지해야 합니다.
• 출력
  • 1번 도시에서 출발하여 나머지 도시로 가는 최단 시간을 출력합니다.
  • 만약, 1번 도시에서 출발하여 특정 도시로 가는 경로가 없다면 -1을 출력하고,
    경로를 통해 무한히 되돌아갈 수 있다면 -1을 출력합니다.

 

문제 설명

아주 전형적인 최단 경로를 찾고, 음수의 사이클을 감지해 예외처리 해주는 벨만-포드 알고리즘입니다.

벨만-포드 알고리즘은 최단 경로 문제를 풀 때, 모든 간선에 대해 최대 V-1번의 반복을 수행하여
각 도시로 가는 최단 거리를 갱신합니다.

 

여기서 V는 도시의 개수입니다.
반복문을 통해 한 번에 여러 경로를 갱신하며,
최종적으로 V-1번의 반복 후, 더 이상 갱신되는 경로가 없다면 알고리즘이 종료됩니다.

 

그러나 만약 V-1번의 반복 후에도 경로가 갱신된다면,
이는 음의 사이클이 존재한다는 의미이며, 이를 감지하여 -1을 출력해야 합니다.

 

주의해야 할 상황은 거리 비교 구문을 int로 두면 안됩니다.(중요! 답과 직결)

음수의 사이클이 만약에 최대로 돌면 under-flow가 일어날 수 있기 때문입니다.

 

 

아래는 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<tuple<int, int, int>> edges;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);


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

	for (int i = 0; i < m; ++i)
	{
		int u, v, cost;
		cin >> u >> v >> cost;
		edges.push_back({ u, v, cost });
	}

	const int inf = 0x3f3f3f3f;

	vector<long long> dist_v(n + 1, inf);

	dist_v[1] = 0;

	for (int i = 1; i < n; ++i)
		for (const auto& [u, v, cost] : edges)
			if (dist_v[u] != inf && dist_v[v] > dist_v[u] + cost)
				dist_v[v] = dist_v[u] + cost;

	for (const auto& [u, v, cost] : edges)
	{
		if (dist_v[u] != inf && dist_v[v] > dist_v[u] + cost)
		{
			cout << -1 << '\n';
			return 0;
		}
	}

	for (int i = 2; i <= n; ++i)
	{
		if (dist_v[i] == inf)
			cout << -1 << '\n';
		else
			cout << dist_v[i] << '\n';
	}


	return 0;
}