[C++]백준 11657번 : 타임머신

www.acmicpc.net/problem/11657

11657번: 타임머신

벨만포드 알고리즘 적용문제.

벨만포드 알고리즘은 최단거리 구하기에서 음이 가중치를 핸들링할 수 있는 알고리즘이다.

음의 사이클이 생기면 최단거리를 구할 수 없고, 이 음의 사이클을 감지할 수 있다.

 

정당성은 다음과 같다.

음수 사이클이 없는 그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다는 점을 떠올리면, 최단 경로가 포함하는 간선 수의 상한을 쉽게 알 수 있다.

• 최단 경로는 최대 |V| 개의 정점을 갖기 때문에 잘 해야 |V| - 1 개의 간선을 가질 수 있다.
• 따라서 모든 간선에 대한 완화(갱신) 과정은 전체 |V| - 1 번이면 충분하다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>

using namespace std;

int N, M, s, d, c;
long long dp[501];
vector<vector<pair<int, long long>>> e;

bool checkChange(){
	for (int j = 1; j <= N; j++){
		if (dp[j] == LLONG_MAX) continue;

		for (int k = 0; k < e[j].size(); k++){
			int dest = e[j][k].first;
			long long cost = dp[j] + e[j][k].second;
			if (dp[dest] > cost){
				return true;
			}
		}
	}
	return false;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	e.resize(N + 1);
	for (int i = 1; i <= N; i++)
		dp[i] = LLONG_MAX;

	for (int i = 0; i < M; i++){
		cin >> s >> d >> c;
		e[s].push_back({ d, c });
	}

	dp[1] = 0;
	for (int i = 0; i < N - 1; i++){ // N-1번
		for (int j = 1; j <= N; j++){ // 모든 정점의
			if (dp[j] == LLONG_MAX) continue;

			for (int k = 0; k < e[j].size(); k++){ // 간선을 탐색한다
				int dest = e[j][k].first;
				long long cost = dp[j] + e[j][k].second;
				if (dp[dest] > cost){
					dp[dest] = cost;
				}
			}
		}
	}

	// N-1번 이후의 탐색에도 최단거리가 갱신되면 음의 사이클이 있다는 뜻
	if (!checkChange()){
		for (int i = 2; i <= N; i++){
			if (dp[i] == LLONG_MAX)
				cout << -1 << "\n";
			else
				cout << dp[i] << "\n";
		}
	}
	else{
		cout << -1;
	}

	return 0;
}

* LLONG_MAX와 관련된 조건문은 문제의 조건에 필요한 코드.