当前位置：首页 > news >正文

打卡信奥刷题（3265）用C++实现信奥题 P8733 [蓝桥杯 2020 国 C] 补给

news 2026/5/15 18:52:48

P8733 [蓝桥杯 2020 国 C] 补给

题目描述

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

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

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

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

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

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

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

输入格式

输入的第一行包含两个整数nnn，DDD，分别表示村庄的数量和单次飞行的距离。

接下来nnn行描述村庄的位置，其中第iii行两个整数xix_ixi，yiy_iyi分别表示编号为iii的村庄的坐标。村庄iii和村庄jjj之间的距离为(xi−xj)2+(yi−yj)2\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}(xi−xj)2+(yi−yj)2。

输出格式

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

输入输出样例 #1

输入 #1

4 6 1 1 4 5 8 5 11 1

输出 #1

28.00

说明/提示

对于所有数据，保证，1≤n≤20,1≤xi,yi≤104,1≤D≤1051\le n\le20,1\le x_i,y_i\le10^4,1\le D\le10^51≤n≤20,1≤xi,yi≤104,1≤D≤105。

蓝桥杯 2020 年国赛 C 组 I 题。

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,d;doubleans=DBL_MAX,x[25],y[25],dp[1<<20][25],dis[25][25];boolvis[25];doublejl(inta,intb){returnsqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));}intmain(){memset(dp,0x7f,sizeofdp);memset(dis,0x7f,sizeofdis);cin>>n>>d;for(inti=0;i<n;i++)cin>>x[i]>>y[i];for(inti=0;i<n;i++)for(intj=0;j<n;j++)if(jl(i,j)<=d)dis[i][j]=jl(i,j);for(inti=0;i<n;i++)for(intj=0;j<n;j++)for(intk=0;k<n;k++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);dp[1][0]=0;for(inti=1;i<(1<<n);i++){for(intj=0;j<n;j++){if(!((i>>j)&1))continue;inttmp=i^(1<<j);for(intk=0;k<n;k++){if(!((tmp>>k)&1))continue;dp[i][j]=min(dp[i][j],dp[tmp][k]+dis[j][k]);}}}for(inti=1;i<n;i++)ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]);printf("%.2lf",ans);return0;}