L - 発電所

L - 発電所解説

実行時間制限: 3 sec / メモリ制限: 1024 MiB

二次元平面上に 1, 2, \ldots, N の番号が付いた N 個の都市があり、都市 i は座標 (X_i, Y_i) にあります。

はじめ、すべての都市に発電所はなく、すべての都市間に電線は張られていません。

あなたは以下の操作を好きな回数行うことができます。

都市 i に発電所を作る。この操作にはコストが P_i かかる。
都市 i と都市 j の間に電線を張る。この操作にはコストが都市間のユークリッド距離、すなわち \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2} かかる。

すべての都市が電線を 0 本以上辿ることで発電所のある都市に辿り着けるようにするためにかかるコストの合計の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
P_1 P_2 \ldots P_N

答えを出力せよ。出力は、真の値との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。

3.00000000000000000000

都市 1, 3 に発電所を作り、都市 1 と都市 2 の間に電線を張ると、コストの合計は 3 となります。

4
0 0
1 1
10 10
50 50
10 10 10 10

31.41421356237309504833

5
0 100000
10000 1000000000
10000 100
1000000000 100000
1000000000 0
400000000 600000000 900000000 200000000 500000000

1200200399.25298526883125305176

There are N cities 1, 2, \ldots, N on a two-dimensional plane. City i is located at coordinates (X_i, Y_i).

Initially, no city has a power plant, and there is no power line between the cities.

You can perform the following operations any number of times:

Build a power plant at city i for a cost of P_i.
Build a power line between cities i and j for a cost of \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2}, the Euclidean distance between them.

Find the minimum total cost required for all cities to be reachable to a city with a power plant via zero or more power lines.

The input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
P_1 P_2 \ldots P_N

Print the answer. Your output is considered correct if and only if the absolute or relative error from the true value is at most 10^{-6}.

3.00000000000000000000

By building a power plant at cities 1 and 3, and a power line between cities 1 and 2, the total cost will be 3.

4
0 0
1 1
10 10
50 50
10 10 10 10

31.41421356237309504833

5
0 100000
10000 1000000000
10000 100
1000000000 100000
1000000000 0
400000000 600000000 900000000 200000000 500000000

1200200399.25298526883125305176