787. Cheapest Flights Within K Stops

It is a very good question

Version #1 Dijkstra
2 bugs
1. the actual K that we push into the minHeap should be K + 1, since we start from src and we count it as one stop but actually it is not a stop
2.TLE for not directly return
My initial implementation was to keep a min price, every time we reach the destination, we compare with min and return in the end
However, we can return price directly once we reached the destination at the first time since the minHeap is comparing price, the path with minimum price will always be poped up first



class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
// Given a minHeap, we are polling out the flights(cities) with shortest distance
// However it is possible that the one with shortest distance cannot satisfy the K stops constraint,
// so we keep pushing flights(cities) with longer distance until we found the cheapest on within K stops
Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
// flights[i][0] from, flights[i][1] to, flights[i][2] price
for (int[] flight : flights) {
graph.putIfAbsent(flight[0], new HashMap<>());
graph.get(flight[0]).put(flight[1], flight[2]);
}
// int[0] -> price from src, int[1] -> city id, int[2] -> remaining stops we can use, >= 0
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparing(a -> a[0]));
minHeap.offer(new int[]{0, src, K + 1});
while (!minHeap.isEmpty()) {
int[] curr = minHeap.poll();
int price = curr[0], city = curr[1], stops = curr[2];
if (city == dst) {
return price;
}
if (stops == 0) continue;
Map<Integer, Integer> neighbors = graph.getOrDefault(city, new HashMap<>());
for (Map.Entry<Integer, Integer> neighbor : neighbors.entrySet()) {
minHeap.offer(new int[]{price + neighbor.getValue(), neighbor.getKey(), stops - 1});
}
}
return -1;
}
}