蓝桥杯 2020 国 C] 补给 题解
MoCaRabbit
·
·
个人记录
这边是一道考试题目，我完全没用 floyd 及其思想。
首先想到，路过一点就必须加满油因为加油不用时间。
所以不用 floyd，直接判断两点直线距离就行了。
这是我们的第一步，贪心。
接下来的转移就简单了，定义状态 dp_{S,i} 为状态为 S 时，现在在村庄 i 的状态。
最开始 dp_{1,1}=0，其它为极大值。
每次将 dp_{S,i} 转移到 dp_{T,j}+dist(i,j)，其中 T 为集合 S 新加上 j 这个元素，当然，根据题意，j 可以是在 S 中的元素。
最后在全集里找一个结束点，使它距离最小即可。
但是还需要回总部，我该怎么办。
首先，这是双向边。
第二，回总部一定走的是最短路。
那还是要最短路算法啊！
但是我们发现，从 $i$ 到 $1$ 的最短路长度一定是从 $1$ 开始又包含 $1$ 又包含 $i$ 的路径的最小值。
发现 $dp$ 数组从 $1$ 开始，支持任意集合的查询。
所以最短路直接可以用 $dp$ 求，然后做完了。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
double d;
int x[30],y[30];
inline double dist(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
double dp[1<<20][20],c[20];
signed main() {
cin>>n>>d;
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
for(int i=0;i<(1<<n);i++) for(int j=0;j<n;j++) dp[i][j]=1e12;
dp[1][0]=0;
for(int i=0;i<(1<<n);i++)//状压
for(int j=0;j<n;j++)
if((1<<j)&i)//属于集合内
for(int k=0;k<n;k++)
if(dist(j+1,k+1)<=d && j!=k)//随便找一个不为 j 的点转移
dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+dist(j+1,k+1));
for(int i=0;i<n;i++) c[i]=1e12;
for(int i=0;i<n;i++) for(int j=0;j<(1<<n);j++) c[i]=min(c[i],dp[j][i]);//找出最短路
double ans=1e12;
for(int i=0;i<n;i++) ans=min(ans,dp[(1<<n)-1][i]+c[i]);//找出答案
printf("%.2f",ans);
return 0;
}
```