# 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)

```java
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 那個

![](/files/A7tpf4HpaHcnXuzXqUFL)

所以 visited 需要是個 memo

T: O(ElogE)

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

```java
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)

```java
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]; 
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/787.-cheapest-flights-within-k-stops-dijsktra-dp.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.