BOJ 1504 특정한 최단 경로 - 계속 WA를 받은 이유

오랜만에 복습도 할겸 다시 풀어봤는데, 계속 틀렸습니다가 나왔다.

이유는 Integer Overflow!!!
int형 변수를 사용하고 있는데, 내가 INF값을 2e9, 즉 20억으로 잡아놓았기 때문에,
경로가 존재하지 않는 경우, INF값이 더해지면서 결과값이 int형 범위를 초과할 수 있다...

게시판 질문에도 나와 같은 케이스가 좀 있어서 그것을 보고 알 수 있었다.
예전에 제출한 코드를 보니 INF를 240만으로 설정해놓았는데, 그 이유는 주어진 간선의 개수가 800개이고, 간선의 가중치(거리)가 최대 1000이라 최단 경로는 최대 (800-1)*1000 가 나오겠지만 여유있게 800*1000=800000(80만)으로 해놓고, 그리고 문제에서 구하는 경로는 3가지 최단 경로로 구성되어 있으므로 80만 * 3 = 240만... 이러면 오버플로우도 일어나지 않는다.