← 返回题目列表

AtCoder · past21_l

L. 发电站

中文机器翻译题面 查看原题

问题陈述

有 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