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

문제 링크

---

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

11657번: 타임머신

 

접근 방법

---

(1) 음수의 가중치가 존재하는 최단 거리 탐색 문제이므로 벨만-포드 알고리즘을 사용하면 된다.

 

(2) 문제에서 요구하는 출력

    1. 사이클의 가중치 합이 음수인 경우

    2. 버스가 도착지에 도달할 수 없는 경우

    3. 문제 없이 버스가 도착지에 도착한 경우

 

(3) (2)에서 요구한 조건을 만족하는 경우

   1. 벨만 포드 알고리즘의 핵심은 3중 for문의 가장 바깥 쪽 for문에서 i == N인 순간 갱신이 일어난다면 말할 것도 없         이 사이클의 가중치 합이 음수인 경우이다.

   2.  dist[j] == INF라면 단 한번도 j번째 지점이 갱신이 일어나지 않았다는 것이다. 즉 j번째 지점에 도착할 수 없다라는         말이 된다. 

   3. 만약 1번 조건에서 걸리게 되면 함수가 return이 되므로 1, 2의 조건에 모두 걸리지 않는다면 버스가 문제 없이

      도착하였다는 뜻이 된다.

 

(4) 주의할 점

 문제에서 주어지는 변수의 범위는 다음과 같다.

 

 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

 

 최악의 경우에서 생각해본다면 1번부터 500번 노드까지 거쳐갈 수 있는 최대 노드의 갯수는 499개이고 가중치 C의 최댓값이 10000이므로 499*10000 이므로 INF는 4990000 이상은 잡아줘야 한다.

 

만약 모든 C가 -10000이면 어떨까? 

for (int i = 1; i <= N; i++) { 
	for (int from = 1; from <= N; from++) {
		for (int j = 0; j < graph[from].size(); j++) {
				//연산 
		}
	}
}

 graph[from].size()가 10 이상 이면 500*500*10*(-10000) = -2,500,000,000 즉 int의 범위를 벗어나 overflow가 발생한다.

그래서 dist는 long long으로 사용해야 적절한 답을 얻을 수 있다.

 

소스 코드

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 0xFFFFFFF

using namespace std;

vector <pair<int, int>> graph[502];
long long dist[502];
int N, M;

void solve() {

	dist[1] = 0;
	bool updated = false;

	for (int i = 1; i <= N; i++) { 
		updated = false;
		for (int from = 1; from <= N; from++) {
			if (dist[from] == INF) 
				continue;
			for (int j = 0; j < graph[from].size(); j++) {
				int to = graph[from][j].first; 
				int cost = graph[from][j].second;
				if (dist[to] > dist[from] + cost) {
					dist[to] = dist[from] + cost;
					updated = true;
				}
			}
		}
		if (i == N) {
			if (updated == true) { // 1.사이클의 가중치 합이 음수인 경우
				cout << -1 << "\n"; 
				return;
			}
		}
	}
	for (int j = 2; j <= N; j++) {
		if (dist[j] == INF)   // 2. 버스가 도달할 수 없는 경우
			cout << -1 << "\n";
		else 		    // 3. 버스가 잘 도착한 경우
			cout << dist[j] << "\n"; 
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < 502; i++) 
		dist[i] = INF;
	
	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		graph[s].push_back({ e,w });
	}
	solve();
}

 

개발 환경 : VS2019

질문, 지적 환영합니다!