787. Cheapest Flights Within K Stops (Dijsktra, DP

Dijsktra use 2 1d visited memo

T: O(ElogE)

S: O(E + V + 2n) , O(e + n + 2n)

class Solution {
    class Pair {
        int node;
        int price;
        int stops;
        Pair (int node, int price, int stops){
            this.node = node;
            this.price = price;
            this.stops = stops;
        }
    }
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<Pair>> graph = buildGraph(flights);
        Queue<Pair> queue = new PriorityQueue<>((a, b) -> a.price - b.price);
        queue.offer(new Pair(src, 0, 0));
        
        // use two memo, to check the price, stop is beter or not
        int[] priceMemo = new int[n];
        int[] stopMemo = new int[n];
        Arrays.fill(priceMemo, Integer.MAX_VALUE);
        Arrays.fill(stopMemo, k+2);
        
        while (!queue.isEmpty()) {
            Pair parent = queue.poll();
            int cur = parent.node;
            int price = parent.price;
            int stops = parent.stops;
            
            if (cur == dst) {
                return price;
            }
            
            if (stops == k+1) { // at most k stops, means visited k+1 edges
                continue;
            }
            for (Pair child : graph.getOrDefault(cur, new ArrayList<>())) {
                int next = child.node;
                int newPrice = price + child.price;
                int newStops = stops+1;
                
                // check the price, stop is beter or not
                if (newPrice < priceMemo[next]) {
                    queue.offer(new Pair(next, newPrice, newStops));
                    priceMemo[next] = newPrice;
                } else if (newStops < stopMemo[next]) {
                    queue.offer(new Pair(next, newPrice, newStops));
                }
                stopMemo[next] = newStops;// stops always update
            }
        }
        return -1;
    }
    private Map<Integer, List<Pair>> buildGraph(int[][] flights) {
        Map<Integer, List<Pair>> graph = new HashMap<>();
        for (int[] flight : flights) {
            graph.computeIfAbsent(flight[0], l -> new ArrayList<>()).add(new Pair(flight[1], flight[2], 0));
        }
        return graph;
    }
}

/*
return the cheapest price

src to dst, at most k stops
*/

Dijsktra use 2d visited memo

為什麼這題不是用一個 visited 就可以了呢

因為不是 pq 排出最小的值就是我們要的答案, 這題還有個 stop, 如果 stop = 0

就只好選大的了 500 那個

所以 visited 需要是個 memo

T: O(ElogE)

S: O(E + V + n*k) , O(e + n + n*k)

class Solution {
    class Pair {
        int node;
        int price;
        int stops;
        Pair (int node, int price, int stops){
            this.node = node;
            this.price = price;
            this.stops = stops;
        }
    }
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<Pair>> graph = buildGraph(flights);
        Queue<Pair> queue = new PriorityQueue<>((a, b) -> a.price - b.price);
        queue.offer(new Pair(src, 0, 0));
        int[][] visited = new int[n][k+2]; // memo value, if new price or stops are not better, don't add to queue
        for (int i = 0; i < n ; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        
        while (!queue.isEmpty()) {
            Pair parent = queue.poll();
            int cur = parent.node;
            int price = parent.price;
            int stops = parent.stops;
            
            if (cur == dst) {
                return price;
            }
            
            if (stops == k+1) {
                continue;
            }
            for (Pair child : graph.getOrDefault(cur, new ArrayList<>())) {
                int next = child.node;
                int newPrice = price + child.price;
                int newStops = stops+1;
                
                if (newPrice < visited[next][newStops]) {
                    queue.offer(new Pair(next, newPrice, newStops));
                    visited[next][newStops] = newPrice;
                } 
            }
        }
        return -1;
    }
    private Map<Integer, List<Pair>> buildGraph(int[][] flights) {
        Map<Integer, List<Pair>> graph = new HashMap<>();
        for (int[] flight : flights) {
            graph.computeIfAbsent(flight[0], l -> new ArrayList<>()).add(new Pair(flight[1], flight[2], 0));
        }
        return graph;
    }
}

/*
return the cheapest price

src to dst, at most k stops
*/

DP

dp[k][to_c] : mini cost to arrive city c by taking k stops flights

dp[k][to_c] = min( dp[k][to_c],  dp[k-1][from] + cost[from][to_c])

T: O(ke)

S: O(kn)

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[][] dp = new int[K+2][n];
        for (int i = 0; i <= K+1; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
            dp[i][src] = 0;
        }
        for (int k = 1; k <= K+1; k++) {
            for (int[] flight : flights) {
                int s = flight[0];
                int d = flight[1];
                int price = flight[2];
                
                // to_dest = min(to_dest, from_src + cost)
                // dp[stops][dest] = min(dp[stops][dest], dp[stops-1][from] + cost)
                if (dp[k-1][s] != Integer.MAX_VALUE) {
                    dp[k][d] = Math.min(dp[k][d], dp[k-1][s]+price);
                }
            }
        }
        return dp[K+1][dst] == Integer.MAX_VALUE ? -1 : dp[K+1][dst]; 
    }
}