1584. Min Cost to Connect All Points ==================================== 题目信息 -------- :题号: 1584 :难度: Medium :主题: 图、最小生成树、曼哈顿距离 :原题: `LeetCode 1584 `_ :重点: 两点连边成本为曼哈顿距离;选择总成本最小的边集,使任意两点之间存在唯一简单路径 题目重述 -------- 给定平面点数组 ``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]``,所有点互不相同。 自建示例 -------- 沿较短边连接可形成最小生成树: .. code-block:: text 输入:points = [[0,0],[2,0],[2,2]] 输出:4 解释:连接前两点成本 2,再连接后两点成本 2,总计 4。 单个点无需任何连接: .. code-block:: text 输入:points = [[5,5]] 输出:0 解释:一个点本身已经连通。