第十一届蓝桥杯（国赛）

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

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

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

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

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

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

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

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

村庄 i i i 和村庄 j j j 之间的距离为 ( x i − x j ) 2 + ( y i − y j ) 2 \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} (xi​−xj​)2+(yi​−yj​)2 ​ 。

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

样例输入 4 6 1 1 4 5 8 5 11 1

样例输出 28.00

数据范围 1 ≤ n ≤ 20 , 1 ≤ x i , y i ≤ 1 0 4 , 1 ≤ D ≤ 1 0 5 1 ≤ n ≤ 20, 1 ≤ x_i, y_i ≤ 10^4, 1 ≤ D ≤ 10^5 1≤n≤20,1≤xi​,yi​≤104,1≤D≤105 。

题解 状压DP + 最短路径：

w[i][j]：从村庄 i 到村庄 j 之间的最短距离； f[i][j]：从村庄 0 走到村庄 j ，且经过经过村庄的状态为 i 的最小飞行距离（将 1 映射成 0，以此类推）；