다익스트라 알고리즘 (1) 썸네일형 리스트형 [Python] 백준 1916번 문제, 최소 비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 우선순위 큐를 사용한 다익스트라를 사용하면 문제를 쉽게 해결할 수 있다. 모든 상황을 고려하는 것보다 우선순위 큐를 사용해 최소 비용들을 갱신하면 속도를 올릴 수 있다. 가중치가 작은 순서대로 정렬되어 있는 우선순위 큐에서 하나씩 꺼내 distance와 city에 값을 넣는다. 그런 다음 cost[city]가 초기화 되어 -1이 아니거나 이미 갱신이 됐지만 dis.. 이전 1 다음