# 787. Cheapest Flights Within K Stops

There are `n` cities connected by `m` flights. Each fight starts from city `u` and arrives at `v` with a price `w`.

Now given all the cities and flights, together with starting city `src` and the destination `dst`, your task is to find the cheapest price from `src` to `dst` with up to `k` stops. If there is no such route, output `-1`.

```
Example 1:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
```

```
Example 2:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.
```

**Note:**

* The number of nodes `n` will be in range `[1, 100]`, with nodes labeled from `0` to `n - 1`.
* The size of `flights` will be in range `[0, n * (n - 1) / 2]`.
* The format of each flight will be `(src, dst, price)`.
* The price of each flight will be in the range `[1, 10000]`.
* `k` is in the range of `[0, n - 1]`.
* There will not be any duplicated flights or self cycles.

{% hint style="info" %}
DFS需要建立一個adjacency list來表示graph，注意helper function裡的pruning。
{% endhint %}

```cpp
// DFS
void helper(vector<vector<vector<int> > >& graph, vector<bool>& visited, int cur, int dst, int K, int out, int& res) {
    if (cur == dst) {
        res = out;
        return;
    }
    if (K < 0) return;
    for (auto& a : graph[cur]) {
        if (visited[a[0]] || out + a[1] > res) continue; // pruning
        visited[a[0]] = true;
        helper(graph, visited, a[0], dst, K - 1, out + a[1], res);
        visited[a[0]] = false;
    }
}
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { // time: O(E + V); space: O(E + V)
    int res = INT_MAX;
    vector<vector<vector<int> > > graph(n); // adjacency list
    vector<bool> visited(n, false);
    visited[src] = true;
    for (auto flight : flights) {
        graph[flight[0]].push_back({flight[1], flight[2]});
    }
    helper(graph, visited, src, dst, K, 0, res);
    return res == INT_MAX ? -1 : res;
}
```

{% hint style="info" %}
BFS也需要建立adjacency list來表示graph，需要queue，注意要做pruning如果當前的價格已經超出目前已求得的res。
{% endhint %}

```cpp
// BFS
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { // time: O(E + V); space: O(E + V)
    int res = INT_MAX, cnt = 0;
    vector<vector<vector<int> > > graph(n); // adjacency list
    // Build graph
    for (auto flight : flights) {
        graph[flight[0]].push_back({flight[1], flight[2]});
    }
    queue<vector<int> > q({{src, 0}}); // queue used for BFS
    while (!q.empty()) {
        for (int i = q.size() - 1; i >= 0; --i) {
            auto t = q.front(); q.pop();
            if (t[0] == dst) res = min(res, t[1]);
            for (auto& a : graph[t[0]]) {
                if (t[1] + a[1] > res) continue;
                q.push({a[0], t[1] + a[1]});
            }
        }
        if (cnt++ > K) break;
    }
    return res == INT_MAX ? -1 : res;
}
```

{% hint style="info" %}
Bellman Ford Algorithm利用Dynamic Programming，其中DP state transition就是relaxation。
{% endhint %}

```cpp
// Bellman Ford Algorithm + DP
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { // time: (K * n^2); space: O(K * n)
    vector<vector<int> > dp(K + 2, vector<int>(n, 1e9));
    dp[0][src] = 0;
    for (int i = 1; i <= K + 1; ++i) {
        dp[i][src] = 0;
        for (auto& flight : flights) {
            dp[i][flight[1]] = min(dp[i][flight[1]], dp[i - 1][flight[0]] + flight[2]); // relaxation
        }
    }
    return (dp[K + 1][dst] >= 1e9) ? -1 : dp[K + 1][dst];
}
```

{% hint style="info" %}
優化空間的使用。
{% endhint %}

```cpp
// Bellman Ford Algorithm + space-optimized DP
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { // time: (K * n^2); space: O(n)
    vector<int> dp(n, 1e9);
    dp[src] = 0;
    for (int i = 0; i < K + 1; ++i) {
        vector<int> t = dp;
        for (auto& flight : flights) {
            t[flight[1]] = min(t[flight[1]], dp[flight[0]] + flight[2]);
        }
        dp = t;
    }
    return dp[dst] >= 1e9 ? -1 : dp[dst];
}
```