<p>There are <code>n</code> cities connected by some number of flights. You are given an array <code>flights</code> where <code>flights[i] = [from<sub>i</sub>, to<sub>i</sub>, price<sub>i</sub>]</code> indicates that there is a flight from city <code>from<sub>i</sub></code> to city <code>to<sub>i</sub></code> with cost <code>price<sub>i</sub></code>.</p>

<p>You are also given three integers <code>src</code>, <code>dst</code>, and <code>k</code>, return <em><strong>the cheapest price</strong> from </em><code>src</code><em> to </em><code>dst</code><em> with at most </em><code>k</code><em> stops. </em>If there is no such route, return<em> </em><code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-3drawio.png" style="width: 332px; height: 392px;" />
<pre>
<strong>Input:</strong> n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
<strong>Output:</strong> 700
<strong>Explanation:</strong>
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-1drawio.png" style="width: 332px; height: 242px;" />
<pre>
<strong>Input:</strong> n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
<strong>Output:</strong> 200
<strong>Explanation:</strong>
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-2drawio.png" style="width: 332px; height: 242px;" />
<pre>
<strong>Input:</strong> n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
<strong>Output:</strong> 500
<strong>Explanation:</strong>
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>0 &lt;= flights.length &lt;= (n * (n - 1) / 2)</code></li>
	<li><code>flights[i].length == 3</code></li>
	<li><code>0 &lt;= from<sub>i</sub>, to<sub>i</sub> &lt; n</code></li>
	<li><code>from<sub>i</sub> != to<sub>i</sub></code></li>
	<li><code>1 &lt;= price<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li>There will not be any multiple flights between two cities.</li>
	<li><code>0 &lt;= src, dst, k &lt; n</code></li>
	<li><code>src != dst</code></li>
</ul>

#if 0
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<array<int, 2>>> graph(n);
        for (vector<int>& f : flights) {
            int &from = f[0], &to = f[1], &cost = f[2];
            graph[from].push_back({to, cost});
        }
        vector<int> minCost(n, 0x3f3f3f3f);
        vector<int> stops(n, 0x3f3f3f3f);
        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> minHeap;
        minCost[src] = 0;
        stops[src] = 0;
        minHeap.push({0, src, 0});
        while (!minHeap.empty()) {
            auto [curCost, curNode, curStops] = minHeap.top();
            minHeap.pop();
            if (curNode == dst) {
                return curCost;
            }
            if (curStops == k + 1) {
                continue;
            }
            for (auto& [nextNode, nextCost] : graph[curNode]) {
                int newCost = curCost + nextCost;
                int newStops = curStops + 1;
                if (newCost < minCost[nextNode] || newStops < stops[nextNode]) {
                    stops[nextNode] = newStops;
                    minCost[nextNode] = newCost;
                    minHeap.push({newCost, nextNode, newStops});
                }
            }
        }
        return -1;
    }
};

// 會給 n 個城鎮, flights[i] = [fromi, toi, pricei] 表示可以從 from 飛到 to 花費 price
// 給你 src, dst, k, 問你能不能經過最多 k 次停靠站 從 src 飛到 dst
// 不能就回傳 -1 可以就回傳最小的成本
// ===

// Q: 想釐清一下 k 停靠站的意思
// 假設 A -> B 我們走到 B 這樣是符合 剛好 1 次嗎?
// 不是
// k 是指 中間的停靠站次數
// 例如 src -> dst 這樣是 0 次, src -> A -> dst 這樣是 1 次

// Q: src, dst 應該都是 在 n 的範圍內 屬於 0 ~ n-1 的整數型態?
// => yes
// Q: 有沒有可能存在cycle? src == dst
// => no
// Q: prices 型態是 整數 浮點數? 值域有沒有可能是負的?
// => int, 不會有負數
// Q: k 的值域?
// => 有可能 0
// Q: 算成本的時候 有沒有可能加總爆 long long?
// => 不會
// Q: flights 有沒有可能出現一樣的元素
// => 應該是有, 但不會存在多條邊

// 這題的話 明顯是要在graph上面找一條成本最低的 path 同時滿足 k 次 停留次數
// 要在 graph 上面找最低成本的path 可以套 dijkstra 演算法
// 方法大概是
// 先假設從一個節點出發 其他節點和他的成本距離之差 一開始都是無限大
// 此時 他有一些鄰居節點可以走 如果此時的成本加上走過去的成本 可以讓 目前成本都變小
// 那就可以放到 priority queue 裡面, 放的時候要順便更新 最低cost
// 下次就從 priority queue 裡面找一個最低成本的 node 
// 取出來後 先看一下 是不是當前最低成本 如果是的話就繼續同樣演算法
// 否則 跳過, 因為這表示 已經有更好的選擇
// 重複這樣演算法 直到找到dst 就可以回傳最低的成本

// 但有個問題是因為還要維護最多只能停靠 k 次
// 所以要改良一下
// 這次放到 pq 的條件要放寬
// 因為 dijkstra 通常是卡一個 如果 cost 比較低才要放入 pq
// 但有一個 case 是 有可能當下存在另一條路徑 雖然 cost 比較高, 但是 停靠的次數比較少
// 意思是 雖然成本高 但是因為停靠次數少 更有可能到達目的
// 如果成本低 但停靠次數提早變成 -1 那沒辦法到達目的地 最後也是沒用
// => 這 bug 卡很久

// 因此要增加另一個放入 pq 的條件: 當停靠次數比較少的時候 也可以塞到 pq
// 就差不多可以寫了

// time: O(Elog(E)*k), E = flight.len
// space: O(E)
#endif

#define INF 0x3f3f3f3f
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> minCost(n, INF);
        minCost[src] = 0;
        for (int limit = 0; limit < k + 1; ++limit) {
            auto preMinCost = minCost;
            for (vector<int>& f : flights) {
                int &from = f[0], &to = f[1], &cost = f[2];
                minCost[to] = min(minCost[to], preMinCost[from] + cost);
            }
        }
        return minCost[dst] == INF ? -1 : minCost[dst];
    }
};

// neetcode
// Bellman-Ford
// 概念上就是用 BFS 去跑, 每次跑滿所有的邊
// 用兩個 minCost 陣列去維護最低的cost, 類似層級更新的概念
// 前一個 minCost 表示前一次的最低 cost, 如果 minCost 和這次cost 可以讓 preMinCost 變更小 就更新
// 跑完一次後 把 minCost 所有的值 update 到 preCost
// 透過這樣的行為跑 k + 1 次後 再看一下 minCost[dst] 是多少
// 類似 dp

// time: O((E + n)*K)
// space: O(n)

#if 0
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<array<int, 2>>> graph(n);
        for (auto& f : flights) {
            int from = f[0], to = f[1], price = f[2];
            graph[from].push_back({to, price});
        }

        vector<int> cost(n, 2e6);
        cost[src] = 0;
        queue<array<int, 2>> q;
        q.push({src, 0});
        
        while (k >= 0) {
            int size = q.size();
            while (size--) {
                auto [from, preCost] = q.front();
                q.pop();
                for (auto& [to, price] : graph[from]) {
                    int newCost = preCost + price;
                    if (newCost < cost[to]) {
                        cost[to] = newCost;
                        q.push({to, newCost});
                    }
                }
            }
            --k;
        }
        return cost[dst] == 2e6 ? -1 : cost[dst];
    }
};

// 給flights 表示flights[i] = [fromi, toi, pricei]
// 還有起點跟終點和k個中繼站
// 問你從起點到終點 經過最多k個中繼站 所花費最便宜的價格是多少?
// 如果沒這樣的路線回傳-1
// ===
// BFS/Dijkstra/floyd

// 好像不能用floyd 因為最多只能走k個中繼站
// floyd是把a -> b的最短花費算出來
// 這點要用Dijkstra處理

// 大概念是每次走的時候 看有哪些路還可以走
// 可以走就放到queue 同時還要記錄走到這邊當下的cost
// 因為要基於這個事實去更新其他可以走的節點
// 接著還要更新所能到達節點的當下的cost

// time: O(E*k) 就是跑滿的概念
// space: O(E)

#endif

#if 0
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<int> dp(n, 2e6);
        int res = 2e6;

        dp[src] = 0;
        // k
        for (int i = 1; i <= k + 1; ++i) {
            // n^2
            auto pre = dp;
            for (auto& f : flights) {
                int from = f[0], to = f[1], price = f[2];
                dp[to] = min(dp[to], pre[from] + price);
                if (to == dst) {
                    res = min(res, dp[to]);
                }
            }
        }

        return res == 2e6 ? -1 : res;
    }
};

// 官神DP space-optimization
#endif

#if 0
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<int>> dp(k + 2, vector<int>(n, 2e6));
        int res = 2e6;

        dp[0][src] = 0;
        // k
        for (int i = 1; i <= k + 1; ++i) {
            // n^2
            for (auto& f : flights) {
                int from = f[0], to = f[1], price = f[2];
                dp[i][to] = min(dp[i][to], dp[i - 1][from] + price);
                if (to == dst) {
                    res = min(res, dp[i][to]);
                }
            }
        }

        return res == 2e6 ? -1 : res;
    }
};

// 官神DP
// 定義 dp[i][b] 表示經過i次轉運站 從a到達b的最少cost
// 那麼 dp[i][b] = min(dp[i][b], dp[i - 1][a] + price);
// 是一個鬆弛的dp寫法
// time: 1e6
// space: 1e4
#endif
16295