2601 問題 C: 藍(lán)橋杯2020年第十一屆國賽真題-補給
時間限制: 3s
內(nèi)存限制: 512MB 提交: 387 解決: 88
題目描述
小藍(lán)是一個直升飛機(jī)駕駛員，他負(fù)責(zé)給山區(qū)的 n n n 個村莊運送物資。
每個月，他都要到每個村莊至少一次，可以多于一次，將村莊需要的物資運送過去。
每個村莊都正好有一個直升機(jī)場，每兩個村莊之間的路程都正好是村莊之間的直線距離。
由于直升機(jī)的油箱大小有限，小藍(lán)單次飛行的距離不能超過 D D D。每個直升機(jī)場都有加油站，可以給直升機(jī)加滿油。
每個月，小藍(lán)都是從總部出發(fā)，給各個村莊運送完物資后回到總部。如果方便，小藍(lán)中途也可以經(jīng)過總部來加油。
總部位于編號為 1 1 1 的村莊。
請問，要完成一個月的任務(wù)，小藍(lán)至少要飛行多長距離？
每個月，他都要到每個村莊至少一次，可以多于一次，將村莊需要的物資運送過去。
每個村莊都正好有一個直升機(jī)場，每兩個村莊之間的路程都正好是村莊之間的直線距離。
由于直升機(jī)的油箱大小有限，小藍(lán)單次飛行的距離不能超過 D D D。每個直升機(jī)場都有加油站，可以給直升機(jī)加滿油。
每個月，小藍(lán)都是從總部出發(fā)，給各個村莊運送完物資后回到總部。如果方便，小藍(lán)中途也可以經(jīng)過總部來加油。
總部位于編號為 1 1 1 的村莊。
請問，要完成一個月的任務(wù)，小藍(lán)至少要飛行多長距離？
輸入
輸入的第一行包含兩個整數(shù) n , D，分別表示村莊的數(shù)量和單次飛行的距離。
接下來 n行描述村莊的位置，其中第 i 行兩個整數(shù) xi , yi 分別表示編號為 i 的村莊的坐標(biāo)。村莊 i 和村莊 j 之間的距離為
接下來 n行描述村莊的位置，其中第 i 行兩個整數(shù) xi , yi 分別表示編號為 i 的村莊的坐標(biāo)。村莊 i 和村莊 j 之間的距離為
輸出
輸出一行，包含一個實數(shù)，四舍五入保留正好 2 2 2 位小數(shù)，表示答案。
樣例輸入
4 6 1 1 4 5 8 5 11 1
樣例輸出
28.00
提示
1≤n≤20,1≤xi,yi≤104,1≤D≤105 。
比賽公告
lanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiaolanqiao