🟦 Prim-4 🏝️《浮空岛传送门费用》

（完全图但不显式给边，边权现场计算：曼哈顿距离）

题目背景

兔猫信奥学院在天空中发现了 $n$ 座浮空岛，第 $i$ 座坐标为 $(x_i,y_i)$。 任意两座岛都能建立传送门，费用按曼哈顿距离计算：

[ w(i,j)=|x_i-x_j|+|y_i-y_j| ]

加菲老师希望用最省的方式把所有岛连通。

题目描述

给定 $n$ 个点坐标，边权按上式定义（完全图）。 输出最小生成树总费用。

输入格式

第一行整数 $n$。 接下来 $n$ 行，每行两个整数 $x_i,y_i$。

输出格式

一个整数：最小总费用。

数据范围

• $2 \le n \le 6000$
• $|x_i|,|y_i| \le 10^9$
• 需要使用 $O(n^2)$ Prim（现场计算边权，不存边）

样例 1

3
0 0
1 0
2 0

2

解释： 选 $1-2(1)$、$2-3(1)$，总费用 2。

样例 2

4
0 0
0 2
3 0
3 2

7

解释： 一种最优：连 $1-2(2)$、$1-3(3)$、$2-4(3)$，总费用 $2+3+3=8$ 不是最优； 更优：连 $1-2(2)$、$3-4(2)$、再连两块之间最便宜边 $1-3(3)$（或 $2-4(3)$），总费用 $2+2+3=7$。