[C++] BOJ 11657 타임머신

문제

백준 11657번 타임머신 https://www.acmicpc.net/problem/11657

11657번: 타임머신

코드

#include<iostream>
#include<vector>
using namespace std;
#define INF 987654321

int m, n;
long long dist[502] = { 0, };
vector <pair<int,int>> bus[502];

int main() {
	//1번 도시 제외하고는 모두 infinity로 거리 설정
	for (int i = 2; i < 502; i++) dist[i] = INF;

	bool negative_cycle = false;

	cin >> n >> m;
	//그래프 입력받음
	while (m--) {
		long long a, b, c;
		cin >> a >> b >> c;
		bus[a].push_back({b, c});
	}

	for (int i = 1; i <= n; i++) {
		for (int start = 1; start <= n; start++) {
			//연결되지 않은 경우
			if (dist[start] == INF)continue;
			
			//연결된 경우
			for (int idx = 0; idx < bus[start].size(); idx++) {
				int end = bus[start][idx].first;
				int cost = bus[start][idx].second;

				if (dist[end] > dist[start] + cost) {
					//negative cycle 존재
					if (i == n) {
						negative_cycle = true;
					}
					//거리 갱신
					dist[end] = dist[start] + cost;
				}
			}
		}
	}

	if (negative_cycle) cout << -1<<'\n';
	else {
		for (int i = 2; i <= n; i++) {
			if (dist[i] == INF) cout << -1 <<'\n';
			else cout << dist[i] << '\n';
		}
	}

}

풀이방법

벨만-포드 알고리즘을 이용한다. 

고민과정

분명히 테스트케이스도 잘 돌아가고, 알고리즘 자체에는 문제가 없어보이는데도 출력초과라고 떠서 구글링을 해본 결과, dist배열을 long long으로 선언해줘야한다는 것을 깨달았다..기본적인 것부터 소홀히 하지 말아야겠다.