Dotcpp  >  编程题库  >  蓝桥杯2020年第十一届国赛真题-补给
题目 2601:

蓝桥杯2020年第十一届国赛真题-补给

时间限制: 5s 内存限制: 576MB 提交: 336 解决: 76

题目描述

小蓝是一个直升飞机驾驶员,他负责给山区的 n n n 个村庄运送物资。

每个月,他都要到每个村庄至少一次,可以多于一次,将村庄需要的物资运送过去。

每个村庄都正好有一个直升机场,每两个村庄之间的路程都正好是村庄之间的直线距离。

由于直升机的油箱大小有限,小蓝单次飞行的距离不能超过 D D D。每个直升机场都有加油站,可以给直升机加满油。

每个月,小蓝都是从总部出发,给各个村庄运送完物资后回到总部。如果方便,小蓝中途也可以经过总部来加油。

总部位于编号为 1 1 1 的村庄。

请问,要完成一个月的任务,小蓝至少要飞行多长距离?

输入格式

输入的第一行包含两个整数 n , D,分别表示村庄的数量和单次飞行的距离。
接下来 n行描述村庄的位置,其中第 i 行两个整数 xi , yi 分别表示编号为 i 的村庄的坐标。村庄 i 和村庄 j 之间的距离为 

输出格式

输出一行,包含一个实数,四舍五入保留正好 2 2 2 位小数,表示答案。

样例输入

4 6
1 1
4 5
8 5
11 1

样例输出

28.00

提示

1≤n≤20,1≤xi,yi≤104,1≤D≤105
标签