[蓝桥杯 2020 国 C] 补给

Luogu
IDLGP8733
Time2000ms
Memory256MB
DifficultyP4
2020蓝桥杯国赛状压 DP
小蓝是一个直升飞机驾驶员,他负责给山区的 $n$ 个村庄运送物资。 每个月,他都要到每个村庄至少一次,可以多于一次,将村庄需要的物资运送过去。 每个村庄都正好有一个直升机场,每两个村庄之间的路程都正好是村庄之间的直线距离。 由于直升机的油箱大小有限,小蓝单次飞行的距离不能超过 $D$。每个直升机场都有加油站,可以给直升机加满油。 每个月,小蓝都是从总部出发,给各个村庄运送完物资后回到总部。如果方便,小蓝中途也可以经过总部来加油。 总部位于编号为 $1$ 的村庄。 请问,要完成一个月的任务,小蓝至少要飞行多长距离? ## Input 输入的第一行包含两个整数 $n$,$D$,分别表示村庄的数量和单次飞行的距离。 接下来 $n$ 行描述村庄的位置,其中第 $i$ 行两个整数 $x_i$,$y_i$ 分别表示编号为 $i$ 的村庄的坐标。村庄 $i$ 和村庄 $j$ 之间的距离为 $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$。 ## Output 输出一行,包含一个实数,四舍五入保留正好 $2$ 位小数,表示答案。 [samples] ## Note 对于所有数据,保证,$1\le n\le20,1\le x_i,y_i\le10^4,1\le D\le10^5$。 蓝桥杯 2020 年国赛 C 组 I 题。
Samples
Input #1
4 6
1 1
4 5
8 5
11 1
Output #1
28.00
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2020 国 C] 补给",
    "description": {
      "content": "小蓝是一个直升飞机驾驶员,他负责给山区的 $n$ 个村庄运送物资。 每个月,他都要到每个村庄至少一次,可以多于一次,将村庄需要的物资运送过去。 每个村庄都正好有一个直升机场,每两个村庄之间的路程都正好是村庄之间的直线距离。 由于直升机的油箱大小有限,小蓝单次飞行的距离不能超过 $D$。每个直升机场都有加油站,可以给直升机加满油。 每个月,小蓝都是从总部出发,给各个村庄运送完物资后回到总部。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8733"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小蓝是一个直升飞机驾驶员,他负责给山区的 $n$ 个村庄运送物资。\n\n每个月,他都要到每个村庄至少一次,可以多于一次,将村庄需要的物资运送过去。\n\n每个村庄都正好有一个直升机场,每两个村庄之间的路程都正好是村庄之间的直线距离。\n\n由于直升机的油箱大小有限,小蓝单次飞行的距离不能超过 $D$。每个直升机场都有加油站,可以给直升机加满油。\n\n每个月,小蓝都是从总部出发,给各个村庄运送完物资后回到总部。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments