問題一覧 > 通常問題

No.1065 電柱 / Pole (Easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-4}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 189
作問者 : 👑 nullnull / テスター : ngtkanangtkana
1 ProblemId : 4230 / 出題時の順位表
問題文最終更新日: 2020-04-26 17:18:16

問題文

null たぷにきあ王国が栄え始めたある日、国王の null くんに電流が走りました!しかし国には電気が通っていませんでした!
不便すぎるのでとりあえず発電所とお城だけでも早急に繋ぎたいと思い、null くんははあなたに電線の消費量の試算を任せました。

電線の消費量は使用した電線候補の長さの和とします。
$N$ 個の電柱 $1, 2, \dots, N$ があり、$i(1 \le i \le N)$ 番目の電柱の座標は $(p_i, q_i)$ です。
$M$ 個の電線候補があり、$j(1 \le j \le M)$ 番目の電線候補は電柱 $P_j$ と電柱 $Q_j$ を線分で結んだものです。
電線はこの候補にしかつけられません。
つけられた電線をいくつかたどることで電柱 $A$ から電柱 $B$ にたどり着くとき、電柱 $A$ と電柱 $B$ は繋がっているといいます。
電線候補をすべて使用したとき、すべての電柱が使われ、繋がることが保証されます。
また、自分から自分への電線候補がないこと、ある $2$ つの電柱を繋げる電線候補は高々 $1$ つであることが保証されます。
あなたの仕事は発電所である電柱 $X$ とお城である電柱 $Y$ を繋げる時の電線の消費量の最小値を求めることです。

入力

$N\ M$
$X\ Y$
$p_1\ q_1$
$p_2\ q_2$
$\dots$
$p_N\ q_N$
$P_1\ Q_1$
$P_2\ Q_2$
$\dots$
$P_M\ Q_M$

$2 \le N \le 2 \times 10^5$
$N - 1 \le M \le min(\frac{N(N - 1)}{2}, 2 \times 10^5)$
$1 \le X, Y \le N$
$X \neq Y$
$-10^3 \le p_i, q_i \le 10^3$
$1 \le P_j, Q_j \le N$
電線候補をすべて使用したとき、すべての電柱が使われ繋がることが保証される。
自分から自分への電線候補がないこと、ある $2$ つの電柱を結ぶ電線候補は高々 $1$ つであることが保証される。
入力はすべて整数である。

出力

電柱候補をいくつか使い電柱 $X$ と電柱 $Y$ を繋げるときの $1$ 番小さい電線使用量を出力してください。
絶対誤差または相対誤差の小さいほうが $10^{-4}$ まで許容されます。
最後に改行してください。

サンプル

サンプル1
入力
5 4
2 4
0 0
-1 -1
1 -1
1 1
-1 1
1 2
1 3
1 4
1 5
出力
2.828427

$2 \sqrt{2}$ です。

サンプル2
入力
10 23
3 7
93 -63
-100 47
-90 -96
-83 32
-15 6
8 57
92 -68
-34 0
76 51
-29 -70
9 10
6 5
5 4
9 3
4 6
5 9
4 9
4 3
1 7
4 8
8 5
8 10
8 7
6 2
3 8
1 8
10 1
10 6
1 5
2 7
3 10
2 10
9 8
出力
193.609552

ここにはありませんが、$2$ つ以上の電柱が全く同じ座標に存在する場合もあります。その場合は電線の使用量が $0$ で繋ぐことができます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。