잘 모르겠지만, 저는 math.inf와 같은 기능을 하는 float('inf')를 사용하여 풀었습니다.

추측을 하자면, math.inf + (어떤 양수) = math.inf 지만, int(1e9) + 어떤 양수 > int(1e9) 여서 그럴수도 있지 않을까 예측을 해봅니다...

다익스트라 알고리즘을 사용하는 다른 문제에서는 

math.inf를 사용해도 괜찮았는데 이 문제에서만 그런 거 보니 더 이해가 안 갑니다 ..ㅠ 

답변주셔서 감사합니다. 

이 문제는, 최단 경로가 여러 개 있을 수도 있다는 점이 중요한 것에서 일반적인 개념 다익스트라 문제과는 살짝 다른거 같습니다...

저 또한 math.inf 로 코드를 작성했기에 33% 부근에서 계속 틀렸다고 나와 원인을 분석해 보았습니다.

s -> x

s -> g -> h -> x

s -> h -> g -> x 

위 세 개가 같으면 정답이 되는 것입니다.

그런데, math.inf 를 사용할 경우 inf + 임의의수 역시 inf 이기 때문에

inf == inf 가 true 가 되어 실제로 경로가 없는 경우 (inf) 임에도 정답으로 추가되어 오답이 됩니다.

도움이 되셨기를 바랍니다.