[백준] 파이썬 17396 - 다익스트라와 1e9
1. 문제 발견https://www.acmicpc.net/problem/17396 오래간만에 다익스트라 알고리즘을 연습하기 위해 푼 문제이다.문제를 풀 때 습관적으로 초기 가중치 값을 1e9로 하고 푸니 틀리게 되었다. https://www.acmicpc.net/board/view/153011질문 게시판을 보니 이 문제에서는 가중치가 1e9 이상 갈 수 있다고 한다. 2. 문제 분석문제에서 정점의 수는 최대 100,000개, 간선의 수는 최대 300,000개, 간선 가중치는 최대 100,000으로 주어졌다.최단 경로의 가중치가 최대로 나올 수 있는 그래프는 다음과 같은 형태의 그래프일 것이다.위 그래프의 최단 거리 가중치를 나이브하게 계산해 보면 100,000 * 100,000 = 10,000,000,0..
2024. 12. 7.
