백준 1854번 K번째 최단경로 찾기

< 백준 1854번 K번째 최단경로 찾기 - 마포 코딩박 >

사용한 알고리즘: 다익스트라

 N개의 도시와, 각 도시간 경로가 입력으로 주어집니다. 1번 도시에서 i번 도시로 가는 K번째 최단경로의 소요시간을 구하는 문제였습니다.

 주의할 점은 1번도시에서 1번도시로 가는 1번째 최단경로의 소요시간은 0임을 출력해주어야 하는 점입니다.

문제풀이는 다음과 같습니다.

(1) (코드 15~16)
 1번도시에서 x번 도시로 가는 경로들의 소요시간을 저장해줄 'pq 배열' 을 만들어줍니다. 큰 값이 위로 오도록 pq를 만들어, 출력 시 맨 위값을 출력해줍니다.

(2) (코드 26~51)
 1번도시에서 x번 도시를 가는 경로의 소요시간을 pair< x번도시, 소요시간> 형태로 pq에 저장하여 소요시간이 작은 것부터 보면서 다익스트라를 구현해 줍니다. 초기값은 <1, 0> 입니다.
 pq에 저장된 값들을 차례로 꺼내 보면서, 해당 값이 과정(1)에 만들어 놓은 pq배열에 최신화 되어 저장되는지 체크합니다. 최신화 된다면 해당 도시와 인접한 도시들을 다시 pq에 저장해 줍니다.

(3) (코드 54~57)
 pq배열에 저장된 소요시간들이 K개보다 적다면 -1을 출력하고, 그렇지 않다면 저장된 값중 가장 큰 값 (맨 위값)을 출력해줍니다.