P8733 [蓝桥杯 2020 国 C] 补给

题目描述

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

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

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

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

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

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

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

输入格式

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

接下来 $n$ 行描述村庄的位置，其中第 $i$ 行两个整数 $x_i$，$y_i$ 分别表示编号为 $i$ 的村庄的坐标。村庄 $i$ 和村庄 $j$ 之间的距离为 $\sqrt{(x_i-x_j{)}^2+(y_i-y_j{)}^2}$。

输出格式

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

输入输出样例 #1

输入 #1

4 6
1 1
4 5
8 5
11 1

输出 #1

28.00

说明/提示

对于所有数据，保证，$1\le n\le 20,1\le x_i,y_i\le 10^4,1\le D\le 10^5$。

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

C++实现

#include <bits/stdc++.h>
using namespace std ;
int n , d ;
double ans = DBL_MAX , x[25] , y[25] , dp[1 << 20][25] , dis[25][25] ;
bool vis[25] ;
double jl(int a , int b)
{
	return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b])) ;
}
int main()
{
	memset(dp , 0x7f , sizeof dp) ;
	memset(dis , 0x7f , sizeof dis) ;
	cin >> n >> d ;
	for(int i = 0 ; i < n ; i++)	
		cin >> x[i] >> y[i] ;
	for(int i = 0 ; i < n ; i++)	
		for(int j = 0 ; j < n ; j++)	
			if(jl(i , j) <= d)	
				dis[i][j] = jl(i , j) ;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < n ; j++)
			for(int k = 0 ; k < n ; k++)
				dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]) ;
	dp[1][0] = 0 ;
	for(int i = 1 ; i < (1 << n) ; i++)
	{
		for(int j = 0 ; j < n ; j++)
		{
			if(!((i >> j) & 1))	continue ;
			int tmp = i ^ (1 << j) ;
			for(int k = 0 ; k < n ; k++)
			{
				if(!((tmp >> k) & 1))	continue ;
				dp[i][j] = min(dp[i][j] , dp[tmp][k] + dis[j][k]) ;
			}
		}
	}
	for(int i = 1 ; i < n ; i++)
		ans = min(ans , dp[(1 << n) - 1][i] + dis[i][0]) ;
	printf("%.2lf" , ans) ;
	return 0 ;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容