Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
最小生成树,Prim


 1 #1584
 2 #Runtime: 7443 ms (Beats 5.2%)
 3 #Memory: 133.3 MB (Beats 51.97%)
 4 
 5 class Solution(object):
 6     def minCostConnectPoints(self, points):
 7         """
 8         :type points: List[List[int]]
 9         :rtype: int
10         """
11         def Distance(p1, p2):
12             return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
13 
14 
15         n = len(points)
16         mp = defaultdict(list)
17         for i in range(n):
18             for j in range(i + 1, n):
19                 d = Distance(points[i], points[j])
20                 mp[i].append((d, j))
21                 mp[j].append((d, i))
22         vis = [0] * n
23         hp = mp[0]
24         vis[0] = 1
25         ans = 0
26         heapq.heapify(hp)
27         while hp:
28             d, i = heapq.heappop(hp)
29             if not vis[i]:
30                 vis[i] = 1
31                 ans += d
32                 for j in mp[i]:
33                     heapq.heappush(hp, j)
34         return ans

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