A40197. 补给
填空题
困难
知识点
题目描述
补给
题目描述
小蓝是一个直升飞机驾驶员，他负责给山区的 n nn 个村庄运送物资。
每个月，他都要到每个村庄至少一次，可以多于一次，将村庄需要的物资运送过去。
每个村庄都正好有一个直升机场，每两个村庄之间的路程都正好是村庄之间的直线距离。
由于直升机的油箱大小有限，小蓝单次飞行的距离不能超过 D DD。每个直升机场都有加油站，可以给直升机加满油。
每个月，小蓝都是从总部出发，给各个村庄运送完物资后回到总部。如果方便，小蓝中途也可以经过总部来加油。
总部位于编号为 1 11 的村庄。
请问，要完成一个月的任务，小蓝至少要飞行多长距离？
输入描述
输出格式
输出一行，包含一个实数，四舍五入保留正好 2 22 位小数，表示答案。
样例输入
4 6
1 1
4 5
8 5
11 1
样例输出
28.00
参考答案
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 20, INF = 1e9;
PII p[N];
int w[N][N], f[1 << N][N];
double get_distance(int i, int j)
{
int x = p[i].first - p[j].first;
int y = p[i].second - p[j].second;
return sqrt(x * x + y * y);
}
int main()
{
int n, d;
cin >> n >> d;
for (int i = 0; i < n; i ++) cin >> p[i].first >> p[i].second;
for (int i = 0; i < n; i ++)
for (int j = i + 1; j < n; j ++)
{
w[i][j] = w[j][i] = get_distance(i, j) * 10000;
if(w[i][j] > d * 10000) w[i][j] = w[j][i] = INF;
}
for (int k = 0; k < n; k ++)
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
for (int i = 0; i < 1 << n; i ++)
for (int j = 0; j < n; j ++)
f[i][j] = INF;
f[1][0] = 0;
for (int i = 0; i < 1 << n; i ++)
for (int j = 0; j < n; j ++)
if(i >> j & 1)
for (int k = 0; k < n; k ++)
if((i - (1 << j)) >> k & 1)
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
int ans = INF;
for (int i = 1; i < n; i ++)
ans = min(ans, w[i][0] + f[(1 << n) - 1][i]);
printf("%.2f", ans / 10000.0);
return 0;
}
上一题
下一题