Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一些航线和价格flights[i] = [fromi, toi, pricei],问从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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理