P8733 [蓝桥杯 2020 国 C] 补给题目描述小蓝是一个直升飞机驾驶员他负责给山区的nnn个村庄运送物资。每个月他都要到每个村庄至少一次可以多于一次将村庄需要的物资运送过去。每个村庄都正好有一个直升机场每两个村庄之间的路程都正好是村庄之间的直线距离。由于直升机的油箱大小有限小蓝单次飞行的距离不能超过DDD。每个直升机场都有加油站可以给直升机加满油。每个月小蓝都是从总部出发给各个村庄运送完物资后回到总部。如果方便小蓝中途也可以经过总部来加油。总部位于编号为111的村庄。请问要完成一个月的任务小蓝至少要飞行多长距离输入格式输入的第一行包含两个整数nnnDDD分别表示村庄的数量和单次飞行的距离。接下来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输入 #14 6 1 1 4 5 8 5 11 1输出 #128.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实现#includebits/stdc.husingnamespacestd;intn,d;doubleansDBL_MAX,x[25],y[25],dp[120][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);cinnd;for(inti0;in;i)cinx[i]y[i];for(inti0;in;i)for(intj0;jn;j)if(jl(i,j)d)dis[i][j]jl(i,j);for(inti0;in;i)for(intj0;jn;j)for(intk0;kn;k)dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);dp[1][0]0;for(inti1;i(1n);i){for(intj0;jn;j){if(!((ij)1))continue;inttmpi^(1j);for(intk0;kn;k){if(!((tmpk)1))continue;dp[i][j]min(dp[i][j],dp[tmp][k]dis[j][k]);}}}for(inti1;in;i)ansmin(ans,dp[(1n)-1][i]dis[i][0]);printf(%.2lf,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容