給出一些航線和價格flights[i] = [from
i, to
i, price
i]，問從src到dst，不超過k次中轉，最低開銷多少，如果無法實現，輸出-1
直接BFS效率還可以，Discussion有更優秀的方法，以后再刷
1 #787
2 #Runtime: 72 ms (Beats 97.24%)
3 #Memory: 15.2 MB (Beats 26.38%)
4
5 class Solution(object):
6 def findCheapestPrice(self, n, flights, src, dst, k):
7 """
8 :type n: int
9 :type flights: List[List[int]]
10 :type src: int
11 :type dst: int
12 :type k: int
13 :rtype: int
14 """
15 f = defaultdict(dict)
16 for x, y, p in flights:
17 f[x][y] = p
18 q = deque([[src, 0]])
19 min_cst = [10000000] * n
20 for j in range(k + 1):
21 len_q = len(q)
22 for _ in range(len_q):
23 [x, cst] = q.popleft()
24 for y in f[x]:
25 t_cst = cst + f[x][y]
26 if t_cst < min_cst[y]:
27 min_cst[y] = t_cst
28 q.append([y, t_cst])
29 if min_cst[dst] == 10000000:
30 return -1
31 return min_cst[dst]