ストーリー

AtCoder社は、最新情報の提供や視聴者との交流を目的とした公式生放送「あーだこーだー」をインターネット上で定期的に配信している。より多くの視聴者に生放送を観てもらいたいと考えた高橋社長は、テレビ用の放送網を構築してAA市の全住民に生放送を配信することにした。

AA市のテレビ配信網は放送局を頂点、放送局間の通信ケーブルを辺とした重み付き平面無向グラフで表現され、座標 $(x_1, y_1) = (0, 0)$ に存在する放送局 $1$ にはAtCoderオフィスが併設されている。各通信ケーブルは電源の ON/OFF を設定可能であり、電源が ON である通信ケーブルのみを経由して放送局 $1$ から到達できる各放送局からは放送用電波を発信することが可能となる。放送用電波の出力強度は各放送局ごとに調整可能であり、出力強度によって生放送を配信可能となる領域が変化する。

通信ケーブルの使用および放送用電波の発信にはコストがかかるため、できるだけコストを抑えつつ、全ての住民に生放送を配信できるような放送網を構築して欲しい。

問題文

$N$ 頂点 $M$ 辺の重み付き平面無向グラフ $G$ が与えられる。頂点 $i$ の座標は $(x_i, y_i)$ であり、辺 $j$ は頂点 $u_j$ と $v_j$ を結ぶ重み $w_j$ の辺である。頂点 $u_j$ と頂点 $v_j$ 間のユークリッド距離を四捨五入したものを $D_j=\\mathrm{round}\\left(\\sqrt{(x_{u_j}-x_{v_j})^2+(y_{u_j}-y_{v_j})^2}\\right)$ とすると、重み $w_j$ は $100D_j\\le w_j\\le 2500D_j$ を満たす。また住民の座標が $K$ 個与えられ、住民 $k$ の座標は $(a_k, b_k)$ である。

各辺について電源の ON/OFF を、各頂点 $i=1,2,\\cdots,N$ について整数値の 出力強度 $P_i\\ (0\\le P_i\\le 5000)$ を設定せよ。 このとき、以下のようにして生放送が配信される。 電源が ON である辺の集合を $E'$ とする。$E'$ に含まれない辺を $G$ から削除した部分グラフ $G'$ を考え、 $G'$ において頂点 $1$ と同一連結成分に含まれる頂点集合を $V'$ とする。 各 $i\\in V'$ について、座標 $(x_i, y_i)$ を中心とした半径 $P_i$ の円形領域内(円周上を含む)に存在する住民が生放送を視聴可能となる。

辺 $j$ の電源を ON に設定すると、コスト $w_j$ が発生する。 また頂点 $i$ の出力強度を $P_i$ に設定すると、コスト $P_i^2$ が発生する。 $i\\notin V'$ である $i$ について $P_i$ を正の値に設定してもよいが、生放送視聴可能な領域は発生せずコストのみが発生する。 全ての住民に生放送を配信しつつコストの総和 $S=\\sum_{i=1}^N{P_i^2}+\\sum_{j\\in E'} w_j$ ができるだけ小さくなるような放送網を構築せよ。

得点

生放送が視聴可能となった住民の数を $n$ 人としたとき、以下の得点が得られる。

• $n\\lt K$ の場合、 $\\mathrm{round}(10^6 \\times (n+1)/K)$
• $n=K$ の場合、 $\\mathrm{round}(10^6\\times(1+10^8/(S+10^7)))$

$S$ が32bit整数型に収まらない場合がある ことに注意せよ。

テストケースは全部で 300 個あり、各テストケースの得点の合計が提出の得点となる。 seed=0 の入力は手動で作成されたものであり、テストケースには含まれない。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWA