11779
-
[백준]11779: 최소비용 구하기2 - JAVA문제풀이/백준 2021. 5. 17. 14:45
[백준]11779: 최소비용 구하기2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 최소 비용을 구하면서, 최소 비용 경로까지 함께 구하는 문제였다. 출발 노드가 정해져 있으므로 다익스트라 알고리즘을 사용하여 출발 노드로 부터 모든 노드까지의 최소 비용을 구해주었다. 처음에는 다익스트라 알고리즘 내부에서 우선순위 큐(최소 힙)에 노드를 넣어 주는 것을 최소 비용 경로로 계산해 주었다. 하지만 이는 정답이 ..