Problem
ある有名な国の政府は、道路網を世界規模で再構築することを決定しました –すでにすべての道路を破壊することに成功しており、今は道路網を再構築する必要があります。新しい双方向道路は、任意の 2 つの都市間に建設できます。道路を建設するコストは、それぞれの都市間の距離に等しくなります。ただし、場合によっては、地形によって異なる価格で道路を建設できる場合があり、そのような都市のペアは特別と呼ばれます。政府はまず、この国の 2 つの主要都市を結ぶことを決定しました。 A と B. あなたは、建設されたすべての道路の総コストができるだけ低くなるように、道路建設の計画を作成するように指示されました。同時に、建設された道路に沿って、 A市からB市へ
入力
最初の行には数値 N – が含まれています。国内の都市の数 (
\(1\leq N\leq10^4\))。次の N 行のそれぞれには、2 つの整数 xi と yi – が含まれています。対応する都市の座標 (
\(|x|, |y| \leq 10^6\) )。以下には、数値 M – が含まれています。都市の特別なペアの数 (
\(0\leq M \leq min(10^4, N(N-1)/2)\). 次の M 行それぞれが 3 つの整数で構成される特別な道路の説明を含む: u、v – 特別な道路が通過する異なる都市のペア、および w – 対応する道路の建設コスト (
\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). 最後の行には、都市 A と B の番号 (1 から N) が含まれています。 br />
インプリント
数字を 1 つ出力します。必要最小限の長さ。あなたの答えは、正しいものと 10
−5 以内で異なる必要があります。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
4
1 1
0 0
10
0 1
1
1 2 100
2 1
| 2.0000000000 |