[Baekjoon] 11675번: 타임머신

🥅 문제

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

 

🔍 설계

음수인 간선이 존재하므로, 벨만 포드 알고리즘을 사용해야 한다. 데이크스트라를 이용한다면 음수 간선으로 인해 거리가 음의 무한대로 계속 갱신되어 무한 루프에 빠지게 된다.

 

기본적인 벨만 포드 식은 Dx(y) = min(Dx(y), Dx(z) + z~y)이다. x에서 y까지의 최소 거리는 x에서 z까지 최소 거리 + z에서 y까지의 거리 중 최솟값이다. 벨만 포드 알고리즘은 벨만 포드 식 적용이 확산된다고 생각하면 된다.

 

물론, 벨만 포드 알고리즘도 사이클로 인해 음의 무한대가 발생할 수 있다. 정점의 개수가 n이라고 할 때, 한 정점에서 다른 정점들까지의 거리를 모두 갱신하는데는 n-1번 모든 간선에 대해 벨만 포드 식을 적용하면 된다. 한 정점에서 어떤 정점으로 가는데 간선을 최대 n-1번 사용하기 때문이다. 그 이상 갱신이 이루어진다면, 음의 간선이 포함된 사이클 때문으로 보면 된다.

 

👊 풀이

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

long long n, m, a, b, c;
vector<long long> dist(501, 1e9 + 7);
vector<vector<int>> edges(6000, vector<int>(3));

bool bf(int start) {
	dist[start] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int cur_node = edges[j][0];
			int next_node = edges[j][1];
			int cost = edges[j][2];
			if (dist[cur_node] != 1e9+7 && dist[next_node] > dist[cur_node] + cost) {
				dist[next_node] = dist[cur_node] + cost;
				if (i == n - 1) {
					return true;
				}
			}
		}
	}
	return false;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> edges[i][j];
		}
	}
	
	bool result = bf(1);
	if (result) {
		cout << -1 << "\n";
	}
	else {
		for (int i = 2; i <= n; i++) {
			if (dist[i] == 1e9 + 7) {
				cout << -1 << "\n";
			}
			else {
				cout << dist[i] << "\n";
			}
		}
	}

	return 0;
}