BOJ 1854 K 번째 최단경로 찾기

 

문제 링크 : https://www.acmicpc.net/problem/1854

1854번: K번째 최단경로 찾기

 

다익스트라 알고리즘을 사용할 때,

priority queue 에서 pop 된 지점은 최단 경로임이 보장되므로

일반적으로는 그 지점을 재차 방문할 이유가 없다.

 

이 문제에서는 k 번째 최단경로를 요구하므로 이미 최단거리가 확보가 된 지점도 다시 방문할 필요가 생겼다.

각 지점에 진입할 때까지의 거리를 다시 기록해 두고 기록한 거리 정보가 k 개를 넘어 섰을 때부터 제거하면 된다.

 

각 지점에서 k 개의 값을 다시 priority queue 에 저장하면 알아서 값들의 크기를 정렬해 준다.

 

자료형 선언

 

보통의 경우라면 초기에 거리를 큰 값으로 초기화하고 개선해서 저장한다.

그리고 저장된 값이 이후 새로이 계산된 값보다 작으면 추가적인 진입을 cut off 하게 된다.

 

하지만 앞서 말한 바와 같이 최단 거리로 cut off 하면 안되니 이 경우에는 Dst 는 초기화하지 않는다.

어차피 k 개까지는 계속 값을 받아들일 것이고 더 이상 갱신될 것이 없을 때까지 계속 정점들을 방문할 것이다.