Leetcode題解 Python & C#：六月挑戰DAY14 Cheapest Flights Within K Stops

有 n 個城市，出發地 src 目的地 dst ，以及航次表 edges : [[cityA(src), cityB(dis), price]...]，最多可轉 K 站到 dis。

要在轉K站之內，找出從 src 到 dst 的最少的總花費，如果沒有則 -1 ，有則回傳花費。

QQ，最近兩天不順，沒有順利解Leetcode，昨日的挑戰也不小心中斷了。

這是一題「Path」題，找路線不外乎就是先把 edge 串連起來，然後再開始找。

 

最常用的是 Dictionary 做映照，如 DP[0] 要映出從 city0 可到的目的地，然後看題目決定要不要雙向，這題是不用雙向。

除了位置的連結，這題還要把花費累積，因此需要不斷從各可能花費取最小的保留。

Python

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        flightMap = defaultdict(list)
        for f in flights:
            flightMap[f[0]].append((f[1], f[2]))
            
        path = dict()
        stack = [(src, 0)] 
        for i in range(K+2):            
            for _ in range(len(stack)):
                start, price = stack.pop(0)    
                if start not in path: path[start] = price
                elif price < path[start]: path[start] = price 
                else: continue
                for f in flightMap[start]:   
                    if dst not in path or price + f[1] < path[dst]:
                        stack.append((f[0], price +  f[1]))
                    
        return path[dst] if dst in path else -1

C#

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        var flightMap = new Dictionary>();
        var priceMap = new Dictionary();
        foreach(var f in flights)
        {
            if (!(flightMap.ContainsKey(f[0]))){flightMap[f[0]] = new Dictionary();}
            flightMap[f[0]].Add(f[1], f[2]);
        }
        
        var queue = new Queue();
        queue.Enqueue(new int[2]{src,0});
        for(int i = 0; i < K + 2; i++)
        {
            int range = queue.Count;
            for(int j = 0; j < range; j++)
            {
                var f = queue.Dequeue();
                if(!(priceMap.ContainsKey(f[0])) || priceMap[f[0]] > f[1])
                {
                    priceMap[f[0]] =  f[1];
                    if (flightMap.ContainsKey(f[0]))
                    {
                        foreach(var nextCity in flightMap[f[0]])
                        {
                            queue.Enqueue(new int[2]{nextCity.Key, f[1] + nextCity.Value});
                        }
                    }
                }
            }
        }
        if (priceMap.ContainsKey(dst)){return priceMap[dst];}
        return -1;