###### tags: `Leetcode` `medium` `graph` `heap` `dynamic programming` `python` `c++`

# 787. Cheapest Flights Within K Stops

## [題目連結:] https://leetcode.com/problems/cheapest-flights-within-k-stops/

## 題目:
There are n cities connected by some number of flights. You are given an array ```flights``` where ```flights[i] = [fromi, toi, pricei]``` indicates that there is a flight from city ```fromi``` to city ```toi``` with cost ```pricei```.

You are also given three integers ```src```, ```dst```, and ```k```, return **the cheapest price** from ```src``` to ```dst``` with at most ```k``` stops. If there is no such route, return ```-1```.


## 解題想法:
* 此題為求從src到dst的最少需要花多少錢，**最多**可以中轉k個休息站。
* 因為k=1，代表可以有一個休息站
* 走A->B->C，可視為走k+1步

## 法1: graph
* **Dijkstra**: 指定一點到其餘各點的最短路徑
* 正常Dijkstra為greedy，紀錄每點是否已拜訪過並逐一取出最小權重更新
* 但此題為變化，需利用k步判斷，所以就不採用額外visited數組紀錄每點是否已經拜訪過
* 改用字典紀錄起始點與已走幾步作為拜訪依據
* **dic**=defaultdict(lambda: float('inf'))
* **key:(src到其他位置,經由幾步到達)**
* **val:cost**
* 補充知識，defaultdict的默認值: item=defaultdict(lambda: "預設")

* 編寫流程:
* use **binary heap**: time: O((|e|+|v|)logV)
* Step1: 建立邊

    edge=defaultdict(list)
    for u,v,w in flights:
        edge[u].append((v,w))

* Step2: 初始所需工具

    dic=defaultdict(lambda: float('inf'))
    #key:(src到其他位置,經由幾步到達) val:cost
    que=[(0, src, 0)] 
    #(目前cost,起點,已經走了幾步)

* Step3-1: while迴圈每次pop出que中權重最小的

    while que:
        cost, curPos, step=heappop(que) 
        #每次pop出cost最小的

* Step3-2: 判斷步數是否合法

    if step>k+1: 
        #若已經超過距離就略過
        continue

* Step3-3: 判斷終止條件

    if curPos==dst:
        return cost

* Step3-4: 更新鄰居

    for neighber, weight in edge[curPos]:
        tmpCost=cost+weight
        #若權重加總小於先前dic中紀錄的，即可更新並加入que
        if tmpCost<dic[(neighber,step+1)]:
            heappush(que, (tmpCost, neighber, step+1))
            dic[(neighber, step+1)]=tmpCost

* Step4: 跳出while結束

    return -1

## Python:

from collections import defaultdict
from heapq import heappush, heappop
class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, k):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type k: int
        :rtype: int
        """
        #dijkstra
        #use binary heap: time: O((|e|+|v|)logV)
        edge=defaultdict(list) #建立邊
        for u,v,w in flights:
            edge[u].append((v,w))
        #key:(src到其他位置,經由幾步到達) val:cost
        #defaultdict的默認值: item=defaultdict(lambda: "預設")
        #或用一般dict.get的用法: dic.get(key,val) val為選填 若該key不存在val為預設值
        dic=defaultdict(lambda: float('inf')) 
        que=[(0, src, 0)] #目前cost,起點,已經走了幾步
        while que:
            cost, curPos, step=heappop(que) #每次pop出cost最小的
            #注意: 因為k=1 代表可以有一個休息站 走A->B->C 可視為走k+1步 
            if step>k+1: 
                #若已經超過距離就略過
                continue
            if curPos==dst:
                return cost
            #更新鄰居
            for neighber, weight in edge[curPos]:
                tmpCost=cost+weight
                if tmpCost<dic[(neighber,step+1)]:
                    heappush(que, (tmpCost, neighber, step+1))
                    dic[(neighber, step+1)]=tmpCost
        return -1
            
    
if __name__=='__main__':
    n =5
    flights =[[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]]
    src =0
    dst =2
    k =2
    result=Solution()
    ans=result.findCheapestPrice(n,flights,src,dst,k)
    print(ans)

## 法2: 使用Dynamic Programming
* **Bellman Ford**
* **dp[i][j]: 從起始位置，走i步能到達j位置的最低價格**
* 初始:
* dp[i][src]=0 (i=0~k+1): 起始位置走i步到起始位置，cost=0
* 轉移方程式:
* 對於每組flights=[curPos, Neighber, weight]
* 每次**更新鄰居**:
* 對於走i步能到達neighber :**dp[i][neighber]**
* dp[i][neighber]=min(原本走i步能到達neighber or **走i-1步達到當前位置curPos，再加上curPos到neighber的weight**)
* dp[i][neighber]=min(dp[i][neighber], dp[i-1][curPos]+weight)

## C++:

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<long int>> dp(k+2, vector<long int>(n, INT_MAX));
        dp[0][src]=0;
        for (int i=1; i<k+2; i++){
            dp[i][src]=0;
            for (auto item: flights){
                int curPos=item[0], neighber=item[1], weight=item[2];
                dp[i][neighber]=min(dp[i][neighber], dp[i-1][curPos]+weight);
            }
        }
        return (dp[k+1][dst]==INT_MAX)? -1: dp[k+1][dst];
    }
};