時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
校園有 N 棟建築物及一些既有網路線。每條線直接連接兩棟建築，長度是兩點直線距離；線可交叉，但只在建築物端點相連。保留所有既有線路，增設最少總長度的新線，使任兩棟建築直接或間接連通。
輸入格式
多組資料至檔案結尾。每組先給 N（1 ≤ N ≤ 750），再給 N 個不同點的整數 x、y，絕對值至多 10000。接著給既有線數 M（0 ≤ M ≤ 1000），再給 M 對建築編號 1 到 N，每對之間至多一條線。
輸出格式
每組輸出新線總長度，四捨五入到小數點後兩位。
題目來源：UVa 10397 — Connect the Campus，CPE 歷屆試題。 原題：https://onlinejudge.org/external/103/10397.pdf
範例測資
範例輸入 1
4 103 104 104 100 104 103 100 100 1 4 2 4 103 104 104 100 104 103 100 100 1 4 2
範例輸出 1
4.41 4.41
請先登入後再提交程式碼
討論與題解
載入討論區…