c525: kevin 的島嶼鏈
標籤 :
通過比率 : 36% (5 人 / 14 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-09-16 17:44

內容

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
3
456 -9
5716 -2677
9088 -4417
範例輸出
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)
]


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