最小生成樹，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