int(1e9) 값이 너무 작은 것 같아요

간선의 수가 최대 30만, t가 최대 10만이니 초기값을 더 크게 해야겟네요. 보통 이런 문제들은 간선 수 * 최대 가중치 값 이상으로 최댓값을 잡습니다.

보통 자료형이나 언어에서 지원하는 최댓값으로 잡는 편이 퍈해요

데이크스트라에서 $INF$값을 잡는다고 하면 그건 아예 도달할 수 없는 정점이라는 의미를 지닌다는 사실을 알고 계실거라 생각합니다. 그러려면, 극단적인 형태의 그래프라 도달할 수 있지만 거리가 엄청나게 긴 상황에서도 그 거리가 $INF$값보다는 작아야 도달할 수 있는 칸과 도달할 수 없는 칸을 구분할 수 있을 것입니다.

본 문제에서는 정점이 최대 $100\,000$개이고 간선의 가중치는 최악 $100\,000$이므로, $0, 1, 2, \cdots, N - 1$번 정점이 차례로 나열된 일직선과 같은 그래프를 생각했을 때의 거리는 $(100\,000 - 1) \times 100\,000$가 될 것이고, 이는 $10^9$를 넘는 수치입니다. 따라서 $INF$값이 되기에 너무 작은 값이 됩니다.

정점의 수가 $V$개, 간선의 최대 가중치를 $D$라고 할 때 $INF$값은 $(V - 1) \times D + 1$ 이상이면 됩니다. 따라서 윗 분께서 제시해주신 $VD$ 이상의 값을 $INF$값으로 잡으시면 문제 없이 공략하실 수 있습니다.

결론: $INF$값으로 큰 값을 잡아야하는 것은 맞으나, 문제에 따라 어느 정도로 이 값이 커야하는 지 다를 수 있으며, 때로는 int 범위를 넘길 수도 있으므로 어느 정도로 큰 값이 필요한지는 알아 두실 것을 권장합니다.

비교 과정에서 설정한 INF 이상의 값이 안 나오기만 하면 됩니다

보통 자료형의 최댓값으로 설정하는데 파이썬에선 딱히 최댓값의 제한이 없기 때문에

float("inf") (모든 유한한 수보다 큼)

float("-inf") (모든 유한한 수보다 작음)

을 사용합니다

파이썬의 int는 무한 정밀도를 제공하기 때문에, 단순히 아키텍처와 관련된 sys.maxsize로는 무한대를 표현하기에는 부족합니다

감사합니다.

여러분들 덕분에 이해했습니다!