[알고리즘/문제풀이] 11657번 타임머신

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

11657번 타임머신 문제의 핵심은 벨만-포드 알고리즘입니다.

벨만-포드 알고리즘에 대한 설명은 다음의 게시물에 있습니다.

2022.01.02 - [알고리즘/이론] - [알고리즘/이론] 벨만-포드 알고리즘

[알고리즘/이론] 벨만-포드 알고리즘

해당 문제는 벨만 포드 알고리즘을 그대로 적용하여 해결할 수 있습니다.

주의사항

• 실제 구현에서 정점까지의 경로가 존재하지 않을 때의 무한대 값을 실제 숫자로 치환하여 구현하기 때문에 최단거리를 완화할 때 "무한대"가 연산이 되지 않도록 주의해야 합니다.
• V-1번 반복하여 간선을 완화하기 때문에 음의 순환이 있을 때 최악의 경우 숫자가 int 형의 범위를 벗어나 언더플로우가 발생할 수 있습니다. 따라서 최단거리 값을 저장할 변수를 long long 형으로 지정해야 합니다.

 

구현(C++)

#include<iostream>
#include<vector>
#include<utility>
#define MAX 0x7fffffff

using namespace std;

int N; //the number of cities
int M; //the number of buses
int A, B, C; //information of bus
vector<pair<int, long long>>vec[500 + 20];

long long dist[500 + 20];

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> A >> B >> C;
		vec[A].push_back(make_pair(B, C));
	}
}

void initial() {
	for (int i = 2; i <= N; i++) {
		dist[i] = MAX;
	}
}

bool bellman(int start) {
	initial();
	for (int i = 0; i < N - 1; i++) {
		for (int j = 1; j <= N; j++) {
			if (dist[j] == MAX) continue;
			for (int k = 0; k < vec[j].size(); k++) {
				int des = vec[j][k].first;
				long long cost = vec[j][k].second;
				if (dist[des] > dist[j] + cost) {
					dist[des] = dist[j] + cost;
				}
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		if (dist[i] == MAX) continue;
		for (int j = 0; j < vec[i].size(); j++) {
			int des = vec[i][j].first;
			long long cost = vec[i][j].second;
			if (dist[des] > dist[i] + cost) return false;
		}
	}

	return true;
}

int main(void) {
	input();
	if (bellman(1) == false) {
		cout << -1 << endl;
	}
	else {
		for (int i = 2; i <= N; i++) {
			if (dist[i] != MAX) {
				cout << dist[i] << endl;
			}
			else {
				cout << -1 << endl;
			}
		}
	}
}