787. Cheapest Flights Within K Stops

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int[] flight : flights) {
            map.put(flight[0], map.getOrDefault(flight[0], new ArrayList<>()));
            map.get(flight[0]).add(new int[]{flight[1], flight[2]});
        }
        int step = 0;
        Queue<int[]> queue = new LinkedList<>();
        int res = Integer.MAX_VALUE;
        queue.offer(new int[]{src, 0});
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                if (cur[0] == dst) {
                    res = Math.min(res, cur[1]);
                }
                if (!map.containsKey(cur[0])) {
                    continue;
                }
                for (int[] flight : map.get(cur[0])) {
                    if (cur[1] + flight[1] > res) {
                        continue; // 强剪枝
                    }
                    queue.offer(new int[]{flight[0], cur[1] + flight[1]});
                }
            }
            if (step > k) {
                break;
            }
            step ++;
        }
        return res == Integer.MAX_VALUE ? -1 :res;
    }
}

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int[] flight : flights) {
            map.put(flight[0], map.getOrDefault(flight[0], new ArrayList<>()));
            map.get(flight[0]).add(new int[]{flight[1], flight[2]});
        }
        // Maintain a PQ to fetch the min cost with max K stops. PQ will have 3 items - 
        //  1. node - The node to visit
        //  2. cost - Cost to visit the node
        //  3. stops - Remaining number of stops to visit destinatio
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        queue.offer(new int[]{src, 0, 0});
        
        // Maintains the minimum number of stops from a particular city. 
        Map<Integer, Integer> seen = new HashMap<>();
        while (!queue.isEmpty()) {
            int[] c = queue.poll();
            int city = c[0];
            int cost = c[1];
            int stops = c[2];
            if (!seen.containsKey(city) || stops < seen.get(city)) {
                seen.put(city, stops);
            } else {
                continue;
            }
            if (city == dst) {
                return cost;
            }
            if (stops > k || !map.containsKey(city)) {
                continue;
            }

            for (int[] next : map.get(city)) {
                queue.add(new int[]{next[0], cost + next[1], stops + 1});
            }
        }
        return -1;
    }
}

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] cost = new int[n];
        Arrays.fill(cost,Integer.MAX_VALUE);
        cost[src] = 0;
        for(int i = 0; i <= k; i++)
        {
            int[] temp = Arrays.copyOf(cost,n);
            for(int[] f: flights) {
                int curr = f[0];
                int next = f[1];
                int price = f[2];
                if (cost[curr] == Integer.MAX_VALUE) {
                    continue;
                }
                temp[next] = Math.min(temp[next], cost[curr] + price);
            }
            cost = temp;
        }
        return cost[dst] == Integer.MAX_VALUE ? -1 : cost[dst];
    }
}