问题陈述
有 N 城市 1, 2, \ldots, N 在二维平面上。 城市 i 位于坐标处 (X_i, Y_i).
最初,没有一个城市有发电厂,城市之间也没有电力线路。
您可以多次执行以下操作:
- 在城市建造一座发电厂 i 费用为 P_i.
- 建设城市之间的电力线 i 和 j 费用为 \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2},它们之间的欧氏距离。
求所有城市通过零个或多个电力线到达拥有发电厂的城市所需的最低总成本。
约束
- 1 \leq N \leq 2000
- 0 \leq X_i, Y_i \leq 10^9
- (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
- 1 \leq P_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N P_1 P_2 \ldots P_N
输出
打印答案。 当且仅当与真实值的绝对或相对误差最多为 10^{-6}.
示例输入 1
3 0 0 1 0 2 2 1 2 1
示例输出 1
3.00000000000000000000
在城市建设发电厂 1 和 3,以及城市之间的电源线 1 和 2,总成本将为 3.
示例输入 2
4 0 0 1 1 10 10 50 50 10 10 10 10
示例输出 2
31.41421356237309504833
示例输入 3
5 0 100000 10000 1000000000 10000 100 1000000000 100000 1000000000 0 400000000 600000000 900000000 200000000 500000000
示例输出 3
1200200399.25298526883125305176