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