백준 1854 K번째 최단경로

BOJ 1854 K번째 최단경로

 

풀이:

1. 도로가 단방향.

2. 시작점은 경로비용 0 (문제에서 제시)

3. 시작점은 1번도시로 고정

이 전제하에 각 도시에 대해 모든 최단경로를 가장 작은 순으로 정렬했을 때 문제에서 주어지는 K번째 경로비용을 구하면 된다.

다만 모든 최단 경로를 구할 경우 메모리 초과가 발생한다.

따라서 모든 경로를 탐색하면서 각 K번째 최단경로까지만 보관한다.

각 경로의 최단경로를 보관하기 위해 입력받는 순간 정렬되는 Priorityque를 배열로 사용한다.

(PriorityQueue<Integer>[] costList = new PriorityQueue[N]; //도시 개수만큼 생성)

que에 들어가는 순간 정렬되는 효과를 이용한다.

적은 비용은 두고 큰 비용은 그거보다 작은 비용을 만날 경우 빼야하므로 역정렬 사용.

new PriorityQueue<>(Collections.reverseOrder());