https://leetcode.com/problems/cheapest-flights-within-k-stops/

cheapest-flights-within-k-stops.java

class Solution {
    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) {
            if (!graph.containsKey(flight[0])) {
                graph.put(flight[0], new HashMap<>());
            }
            graph.get(flight[0]).put(flight[1], flight[2]);
        }
        
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->(Integer.compare(a[0], b[0])));
        queue.offer(new int[]{0, src, 0});
        while(!queue.isEmpty()) {
            int[] curr = queue.poll();
            int cost = curr[0];
            int loc = curr[1];
            int step = curr[2];
            
            if (loc == dst) {
                return cost;
            }
            Map<Integer, Integer> neighbors = graph.get(loc);
            if (neighbors == null || step > K) {
                continue;
            }
            for (Map.Entry<Integer, Integer> entry : graph.get(loc).entrySet()) {
                int nextLoc = entry.getKey();
                int nextCost = entry.getValue();
                queue.offer(new int[]{cost + nextCost, nextLoc, step + 1});
            }
        }
        return -1;
    }
}