有 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;