2601 問題 C: 藍橋杯2020年第十一屆國賽真題-補給
時間限制: 3s
內(nèi)存限制: 512MB 提交: 387 解決: 88
題目描述
小藍是一個直升飛機駕駛員，他負責(zé)給山區(qū)的 n n n 個村莊運送物資。
每個月，他都要到每個村莊至少一次，可以多于一次，將村莊需要的物資運送過去。
每個村莊都正好有一個直升機場，每兩個村莊之間的路程都正好是村莊之間的直線距離。
由于直升機的油箱大小有限，小藍單次飛行的距離不能超過 D D D。每個直升機場都有加油站，可以給直升機加滿油。
每個月，小藍都是從總部出發(fā)，給各個村莊運送完物資后回到總部。如果方便，小藍中途也可以經(jīng)過總部來加油。
總部位于編號為 1 1 1 的村莊。
請問，要完成一個月的任務(wù)，小藍至少要飛行多長距離？
每個月，他都要到每個村莊至少一次，可以多于一次，將村莊需要的物資運送過去。
每個村莊都正好有一個直升機場，每兩個村莊之間的路程都正好是村莊之間的直線距離。
由于直升機的油箱大小有限，小藍單次飛行的距離不能超過 D D D。每個直升機場都有加油站，可以給直升機加滿油。
每個月，小藍都是從總部出發(fā)，給各個村莊運送完物資后回到總部。如果方便，小藍中途也可以經(jīng)過總部來加油。
總部位于編號為 1 1 1 的村莊。
請問，要完成一個月的任務(wù)，小藍至少要飛行多長距離？
輸入
輸入的第一行包含兩個整數(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 。
比賽公告
Tips：
請對本次比賽進行一些描述，公告內(nèi)容應(yīng)當(dāng)包含：
比賽的創(chuàng)辦者或組織；
本次比賽的目的或意義；
本次比賽的考點、語言或類型；或其他注意事項及描述等。
至少保證30個漢字長度。