❓문제 설명

문제 : 백준 11657번 타임머신
난이도 : 골드 4

문제 요약

• N개의 도시, M개의 버스가 존재합니다.
• A는 시작도시, B는 도착도시, C는 버스 이동 시간입니다. 이때 C는 음수일 수 도 있습니다.
• C가 0일 때는 순간이동, C가 0보다 작을 때는 타임머신으로 시간을 되돌아가는 경우입니다.
• 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 출력하면됩니다.
• 시간이 무한히 오래 전으로 되돌릴 수 있으면 -1을 출력합니다.
• 해당 도시로 가는 경로가 없을 때도 -1을 출력합니다.

🎯문제 해결 방법

이 문제는 타임머신을 타면 음수의 비용도 존재하기 때문에 벨만-포드 알고리즘을 이용해서 풀어야하는 문제입니다. 최소 비용을 구하는 또다른 알고리즘인 다익스트라 알고리즘은 음수 가중치가 존재할 때는 사용할 수 없으므로 벨만-포드 알고리즘을 사용해야합니다.

for(int i=1; i<=n-1; i++) {
	for(int j=0; j<v.size(); j++){
		int st = v[j].first.first;
		int en = v[j].first.second;
		int cost = v[j].second;
		if(dist[st] == 1e9) continue;
		if(dist[en] > dist[st] + cost) dist[en] = dist[st] + cost;
	}
}

벨만-포드 알고리즘은 N-1번 반복하면 모든 도시와의 최소 거리를 구할 수 있는 특징을 이용합니다.

for(int j=0; j<v.size(); j++){
	int st = v[j].first.first;
	int en = v[j].first.second;
	int cost = v[j].second;
	if(dist[st] == 1e9) continue;
	if(dist[en] > dist[st] + cost){
		cout << -1;
		return;
	}
}

N-1번 반복하고 한번을 더 확인해줍니다. 이유는 N-1번을 하고도 한번더 했을 때 가중치의 값이 더 작아지는 도시가 있다면 음의 사이클이 존재한다고 여기기 때문입니다. 문제에서 무한히 오래 전으로 되돌릴 수 있으면 -1을 출력한다는 말은 음의 사이클이 존재하면 -1을 출력한다와 같은 말입니다.

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

그런 뒤 1번 도시에서 다른 도시들까지의 최소 비용을 출력해줍니다.

💻전체 코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
ll dist[504];
int n,m;
vector<pair<pair<int,int>, int>> v;

void belman() {
	dist[1] = 0;
	for(int i=1; i<=n-1; i++) {
		for(int j=0; j<v.size(); j++){
			int st = v[j].first.first;
			int en = v[j].first.second;
			int cost = v[j].second;
			if(dist[st] == 1e9) continue;
			if(dist[en] > dist[st] + cost) dist[en] = dist[st] + cost;
		}
	}
	
	for(int j=0; j<v.size(); j++){
		int st = v[j].first.first;
		int en = v[j].first.second;
		int cost = v[j].second;
		if(dist[st] == 1e9) continue;
		if(dist[en] > dist[st] + cost){
			cout << -1;
			return;
		}
	}
	for(int i=2; i<=n; i++){
		if(dist[i] == 1e9) cout << -1 << '\n';
		else cout << dist[i] << '\n';
	}
}

int main(void){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	
	for(int i=0; i<=500; i++) dist[i] = 1e9;
	
	for(int i=0; i<m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v.push_back({{a,b}, c});
	}
	
	belman();
	return 0;
}