11657 타임머신 (골드 4)

벨만-포드 알고리즘을 그냥 구현하면 되는 문제이다.

나는 https://yabmoons.tistory.com/365 이 사이트를 참고했다.

벨만-포드 알고리즘을 설명해주는 사이트지만 거의 정답..!! 엄청 잘 설명되어있다.

벨만-포드 알고리즘의 핵심은 계산된 노드만 본다 & N-1번 반복 두 개!

 

 

문제 설명을 하자면 From, To, Cost가 주어지고 1번 node에서 다른 node까지의 최소 거리를 구하는 문제이다.

근데 음의 사이클이 하나라도 존재한다면 -1을 출력해야 한다.

 

 

 

한 가지 문제가 발생했던 부분은 자꾸 출력 초과가 발생했던 문제였다.

문제 검색에 찾아보니 underflow 때문에 발생하는 문제였다.

dist의 자료형을 int->long으로 변경했더니 문제가 해결됐다.

 

 

// 타임머신 (골드 4)

//dist를 long으로 안하면 출력 초과가 남 ( underflow 때문에 )

#include <iostream>
#include <limits>

using namespace std;

int N, M;
pair<pair<int, int>, int>* graph;
long* dist;

void Bellman_Ford() {
	int From, To, cost;

	dist[1] = 0;
	
	for (int i = 0;i < N + 1;i++) { //N+1번 반복
		for (int j = 0;j < M;j++) {
			
			From = graph[j].first.first;
			To = graph[j].first.second;
			cost = graph[j].second;

			if (dist[From] == numeric_limits<int>::max()) continue; // 한 번도 방문x 넘김

			if (dist[To] > dist[From] + cost) {
				dist[To] = dist[From] + cost;
			}
		}
	}

	for (int i = 0; i < M;i++) {
		From = graph[i].first.first;
		To = graph[i].first.second;
		cost = graph[i].second;

		if (dist[From] == numeric_limits<int>::max()) continue;
		if (dist[To] > dist[From] + cost) {
			cout << "-1"; return;
		}
	}

	for (int i = 2;i < N + 1;i++) {
		if (dist[i] == numeric_limits<int>::max()) cout << "-1" << '\n';
		else cout << dist[i] << '\n';
	}


}


int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	graph = new pair<pair<int, int>, int>[M];

	dist = new long[N + 1]{};

	for (int i = 0;i < M;i++) {  // From To cost 입력
		cin >> graph[i].first.first >> graph[i].first.second >> graph[i].second;
	}

	for (int i = 1;i < N + 1;i++) {
		dist[i] = numeric_limits<int>::max(); // 거리 inf
	}

	Bellman_Ford();

	delete[] graph, dist;

	return 0;
}

// 2212KB, 8ms