給出一些航線和價(jià)格flights[i] = [from
i, to
i, price
i]，問(wèn)從src到dst，不超過(guò)k次中轉(zhuǎn)，最低開(kāi)銷多少，如果無(wú)法實(shí)現(xiàn)，輸出-1
直接BFS效率還可以，Discussion有更優(yōu)秀的方法，以后再刷
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]