c525. kevin 的島嶼鏈 - 高中生程式解題系統

內容

kevin 買了n座小島，每個島有X座標與Y座標，

他想將些島連起來，可是kevin很窮，他想花儘量少的錢

現在請你找到一個n的排列(P1, P2, P3, ..., Pn)，使得P1島建橋到P2島、P2島建橋到P3島、....、Pn-1島建橋到Pn島的花費總和最小

花費為兩島的直線距離

輸入說明

第一行有一個數字t，代表測資筆數

每一筆測資第一行為n，代表島的數量

接下來n行每一行有兩個整數，為每座島的X座標與Y座標

100%的測資滿足 t <= 5

100%的測資滿足 -10000 < X, Y < 10000

20%的測資滿足n <= 3

60%的測資滿足n <= 15

99%的測資滿足n <= 20

100%的測資滿足n <= 25

輸出說明

對於每一筆測資請輸出一行，代表最小花費，答案請四捨五入到小數點後第二位

範例輸入 #1

範例輸出 #1

9692.42

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 5.0s , <1K
公開測資點#1 (40%): 5.0s , <1K
公開測資點#2 (39%): 5.0s , <1M
公開測資點#3 (1%): 5.0s , <1M

提示：

標籤:

出處:

[管理者： bl33234679 (StillFantasy) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」