【力扣】（中等）787. K 站中轉内最便宜的航班 --- 動态規劃

• 787 K 站中轉内最便宜的航班

• 有 n 個城市通過 m 個航班連接配接。每個航班都從城市 u 開始，以價格 w 抵達 v。

  現在給定所有的城市和航班，以及出發城市 src 和目的地 dst，你的任務是找到從 src 到 dst 最多經過 k 站中轉的最便宜的價格。 如果沒有這樣的路線，則輸出 -1。

  來源：力扣（LeetCode）

  連結：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops

解題思路：動态規劃，dp[i][k]是指到達i城市至多需要k步的最小費用，明顯dp[src][k]=0,0<=k<=K+1，從k=1開始，周遊整個flights，目前航班為flight，如果存在k-1步從src抵達目前航班的起點站flight[0]（即費用dp[flight[0]][k-1]不等于無窮大），則更新目前航班終點站flight[1]的費用dp[flight[1]][k] = min(dp[flight[1]][k] , dp[flight[0]][k-1]+ flight[2])。k加一，重複以上步驟，直至k=K+1。最終傳回dst的費用，即dp[dst][K+1]。

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<int>> dp(n, vector<int>(K+2, INT_MAX));
        for(int i =0; i<K+2; ++i){
            dp[src][i] = 0;
        }
        for(int i=1; i<K+2; ++i){
            for(auto flight : flights){
                if(dp[flight[0]][i-1]!=INT_MAX){
                    dp[flight[1]][i] = min(dp[flight[1]][i], dp[flight[0]][i-1] + flight[2]);
                }
            }
        }
        if(dp[dst][K+1]==INT_MAX) return -1;
        return dp[dst][K+1];
    }
};