백준 11657번 타임머신

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

문제풀이
사용한 알고리즘: 밸만 포드
오랫만에 봤는데 재채점 후 '출력초과' 가 떠서 다시 풀고 작성합니다....

(1) 코드 15~20

 입력으로 주어지는 a도시에서 b 도시 가는 시간 c 를 pair 형태로 vector에 저장합니다.

(2) 코드 21~36

 'dist[k] : 1번도시에서 k번도시 가는 데 드는 시간' 이라고 설정한 뒤, dist[1]=0 라고 설정합니다. 
 도시개수가 N개이니 N-1번 밸만포드를 돌리면 모든 도시의 최적 시간이 갱신됩니다.
 만약 N번째 돌릴때 갱신이 된다면, minus cycle 이 존재하는 것입니다.

(3) 코드 38~44

 minus cycle 의 유무에 따라 문제에서 원하는 답을 출력해줍니다.

(4) 왜 '출력초과'로 재채점 되었는가?

 모르겠습니다.... 

 한번 이동의 최대 시간이 10^4, 최대 도시 수가 500이라 int 범위 내로 해결이 된다 생각하였으나, 어느 과정에선가 int 범위를 넘어가서 수가 터진 것 같습니다...

 실제로 기존 풀이에서 long long 으로 바꿔줬더니 AC를 받았습니다.

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	typedef pair<int, ll> pii;
	const int MAX = 505;
	const ll INF = 1987654321987654321;
	int N, M;
	ll dist[MAX];
	vector<pii> adj[MAX];
	int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
	int a, b;
	ll d;
	cin >> a >> b >> d;
	adj[a].push_back(pii(b, d));
	}
	fill(dist, dist + MAX, INF);
	dist[1] = 0LL;
	bool minuscycle = false;
	for (int k = 0; k < N; ++k) {
	for (int i = 1; i <= N; ++i) {
	if (dist[i] == INF) continue;
	for (auto it : adj[i]) {
	int next = it.first;
	ll d = it.second;
	if (dist[i] + d < dist[next]) {
	dist[next] = dist[i] + d;
	if (k == N - 1) minuscycle = true;
	}
	}
	}
	}
	if (minuscycle) cout << -1 << '\n';
	else {
	for (int i = 2; i <= N; ++i) {
	if (dist[i] == INF) cout << -1 << '\n'; // 1번도시에서 i도시에 가는 길 없음
	else cout << dist[i] << '\n';
	}
	}
	return 0;
	}

view raw BOJ 11657.cpp hosted with ❤ by GitHub