title
You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].
| The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: | xi - xj | + | yi - yj | , where | val | denotes the absolute value of val. |
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
Example 1:
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation:
We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.
Example 2:
Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18
Example 3:
Input: points = [[0,0],[1,1],[1,0],[-1,1]]
Output: 4
Example 4:
Input: points = [[-1000000,-1000000],[1000000,1000000]]
Output: 4000000
Example 5:
Input: points = [[0,0]]
Output: 0
Constraints:
1 <= points.length <= 1000
-106 <= xi, yi <= 106
All pairs (xi, yi) are distinct.
solution
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
uf = {}
def find(x):
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def union(a, b):
uf[find(a)] = find(b)
def is_connect(a, b):
return find(a) == find(b)
uf = {x: x for x in range(len(points))}
import heapq
edges = []
import math
for i in range(len(points)):
for j in range(i):
edges.append((i, j, math.fabs(points[i][0] - points[j][0]) + math.fabs(points[i][1] - points[j][1])))
class Q:
def __init__(self, a, b, v):
self.a, self.b, self.v = a, b, v
def __lt__(self, other):
return self.v < other.v
queue = [Q(e[0], e[1], e[2]) for e in edges]
heapq.heapify(queue)
# edges = sorted(edges, key=lambda x: x[2])
# print("edges: ", edges)
res = int(0)
while len(queue)>0:
# for e in edges:
e = heapq.heappop(queue)
a, b, v = e.a, e.b, e.v
if is_connect(a, b):
continue
else:
res += v
union(a, b)
# print("res: ", res)
return int(res)