package ch13;

import java.util.*;

public class P045_2 {

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {

// 여행 경로를 출발지 → 도착지 형태의 그래프로 구성

Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();

for (int[] flight : flights) {

// 값이 존재하지 않을 경우 빈 해시맵 생성

graph.putIfAbsent(flight[0], new HashMap<>());

// 출발지에 (도착지, 비용) 추가

graph.get(flight[0]).put(flight[1], flight[2]);

}

// 우선순위 큐 생성, 값은 (도착지, 비용, 진행 경로)로 구성하므로, 정렬은 비용(인덱스 1) 기준

Queue<List<Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.get(1)));

// (도착지, 비용, 진행 경로)을 큐에 삽입, 시작은 출발지 src이며, 비용과 진행 경로는 출발지이므로 당연히 모두 0

pq.add(Arrays.asList(src, 0, 0));

// 타임아웃을 방지하기 위해 한 번 방문한 경로는 저장해두는 맵 선언

Map<Integer, Integer> visited = new HashMap<>();

// 큐에 값이 남아 있다면 없어질 때 까지 반복

while (!pq.isEmpty()) {

// 비용이 가장 저렴한 값 추출

List<Integer> cur = pq.poll();

// 우선순위 큐의 항목은 List<Integer>이므로 인덱스 위치로 (도착지, 비용, 진행 경로) 각각 추출

int u = cur.get(0);

int price_u = cur.get(1);

int k_visited = cur.get(2);

// 만약 큐에서 추출한 값이 도착지 dst라면 정답으로 리턴

if (u == dst) return price_u;

// 도착지(u)까지 진행 경로(k_visited) 저장, 따로 저장해두진 않지만 비용(price_u)이 가장 저렴한 경로다.

visited.put(u, k_visited);

// 진행 경로(k_visited)가 남은 경로(k) 이내에 있다면 처리 계속

if (k_visited <= k) {

// 처리하면서 진행 경로 +1

k_visited += 1;

// u 지점을 출발지로 한 경로가 있다면 처리 시작

if (graph.containsKey(u)) {

// u 지점을 출발지로 한 모든 경로 순회

for (Map.Entry<Integer, Integer> v : graph.get(u).entrySet()) {

// 이미 계산한 경로는 큐에 삽입하지 않는 형태로 풀이를 최적화한다.

// 그러나 아직 계산한 경로가 아니거나, 진행 경로(k_visited)가 기존보다 작다면 도착지(dst)까지는

// 또 다른 최소 비용을 계산할 가능성이 있으므로 큐에 삽입하여 한 번 더 계산 진행

if (!visited.containsKey(v.getKey())

|| k_visited < visited.get(v.getKey())) {

// u 지점까지 비용(price_u) + u 지점을 출발지로 한 도착지까지 비용

int alt = price_u + v.getValue();

// 우선순위 큐에 (도착지, 비용, 진행 경로) 삽입

pq.add(Arrays.asList(v.getKey(), alt, k_visited));

}

}

}

}

}

// 큐의 모든 값이 비워질 때까지 리턴하지 못했다면 경로가 존재하지 않는다는 얘기이므로 -1 리턴

return -1;

}

}