1584. Min Cost to Connect All Points¶
题目信息¶
- 题号:
1584
- 难度:
Medium
- 主题:
图、最小生成树、曼哈顿距离
- 原题:
- 重点:
两点连边成本为曼哈顿距离;选择总成本最小的边集,使任意两点之间存在唯一简单路径
题目重述¶
给定平面点数组 points。连接两点 [x_i,y_i] 与 [x_j,y_j] 的成本为 |x_i-x_j| + |y_i-y_j|。
请选择若干连接,使全部点连通,并且任意两点之间恰好存在一条简单路径。返回最小总成本。
1 <= points.length <= 1000,坐标位于 [-10^6,10^6],所有点互不相同。
自建示例¶
沿较短边连接可形成最小生成树:
输入:points = [[0,0],[2,0],[2,2]]
输出:4
解释:连接前两点成本 2,再连接后两点成本 2,总计 4。
单个点无需任何连接:
输入:points = [[5,5]]
输出:0
解释:一个点本身已经连通。