백준 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를 받았습니다.