In a two-dimensional plane, there are $N$ towns and $M$ chests. Town $i$ is at the coordinates $(X_i,Y_i)$, and chest $i$ is at the coordinates $(P_i,Q_i)$. Takahashi will go on a trip where he starts at the origin, visits all $N$ towns, and then returns to the origin. Takahashi's initial moving speed is $1$. Find the shortest time needed to complete the trip.Problem Statement
It is not mandatory to visit chests, but each chest contains an accelerator. Each time he picks up an accelerator, his moving speed gets multiplied by $2$.Constraints
Input
The input is given from Standard Input in the following format:
$N$ $M$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$ $P_1$ $Q_1$ $\vdots$ $P_M$ $Q_M$
Output
Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most $10^{-6}$.
Sample Input 1
2 1 1 1 0 1 1 0
Sample Output 1
2.5000000000
Here is one optimal way to complete the trip.
- Go the distance $1$ from the origin to chest $1$ at a speed of $1$, taking a time of $1$.
- Go the distance $1$ from chest $1$ to town $1$ at a speed of $2$, taking a time of $0.5$.
- Go the distance $1$ from town $1$ to town $2$ at a speed of $2$, taking a time of $0.5$.
- Go the distance $1$ from town $2$ to the origin at a speed of $2$, taking a time of $0.5$.
Sample Input 2
2 1 1 1 0 1 100 0
Sample Output 2
3.4142135624
Here is one optimal way to complete the trip.
- Go the distance $1.41\ldots$ from the origin to town $1$ at a speed of $1$, taking a time of $1.41\ldots$.
- Go the distance $1$ from town $1$ to town $2$ at a speed of $1$, taking a time of $1$.
- Go the distance $1$ from town $2$ to the origin at a speed of $1$, taking a time of $1$.
Sample Input 3
1 2 4 4 1 0 0 1
Sample Output 3
4.3713203436
Here is one optimal way to complete the trip.
- Go the distance $1$ from the origin to chest $1$ at a speed of $1$, taking a time of $1$.
- Go the distance $1.41\ldots$ from chest $1$ to chest $2$ at a speed of $2$, taking a time of $0.707\ldots$.
- Go the distance $5$ from chest $2$ to town $1$ at a speed of $4$, taking a time of $1.25$.
- Go the distance $5.65\ldots$ from town $1$ to the origin at a speed of $4$, taking a time of $1.41\ldots$.
这个数据范围，考虑状压dp。
定义 \(dp_{i,j,k}\) 表示走过了集合 \(i\) 的 towns，集合 \(j\) 的 chests,现在到了 \(k\) 点的最短距离。（不妨用 \(n+i\) 表示第 \(i\) 个chests）
然后就可以枚举下一个去哪里，转移应该很简单了。就是算出两点之间的距离，除以 \(j\) 的元素个数就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=13,M=6;
double dp[1<<N][1<<M][N+M],ans;
int n,m,x[N+M],y[N+M],pw[6];
long long sqr(int a)
{
return 1LL*a*a;
}
double dist(int a,int b)
{
return sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));
}
int popcnt(int x)
{
int cnt=0;
while(x)
cnt+=x&1,x>>=1;
return cnt;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=0;i<m;i++)
scanf("%d%d",&x[i+n],&y[i+n]);
for(int i=pw[0]=1;i<=5;i++)
pw[i]=pw[i-1]*2;
for(int i=0;i<(1<<N);i++)
for(int j=0;j<(1<<M);j++)
for(int k=0;k<(N+M);k++)
dp[i][j][k]=1e16;
for(int i=0;i<n;i++)
dp[1<<i][0][i]=dist(n+m,i);
for(int i=0;i<m;i++)
dp[0][1<<i][i+n]=dist(n+m,i+n);
ans=1e16;
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<(1<<m);j++)
{
int k=popcnt(j);
for(int x=0;x<n;x++)
{
if(!(i>>x&1))
continue;
for(int y=0;y<n;y++)
{
if(x==y||!(i>>y&1))
continue;
dp[i][j][x]=min(dp[i][j][x],dp[i^1<<x][j][y]+dist(x,y)/pw[k]);
}
for(int y=n;y<m+n;y++)
{
if(!(j>>(y-n)&1))
continue;
dp[i][j][x]=min(dp[i][j][x],dp[i^1<<x][j][y]+dist(x,y)/pw[k]);
}
if(i==(1<<n)-1)
ans=min(ans,dp[i][j][x]+dist(x,n+m)/pw[k]);
// printf("%d %d %d %.6lf\n",i,j,x,dp[i][j][x]) ;
}
--k;
for(int x=0;x<m;x++)
{
if(!(j>>x&1))
continue;
for(int y=0;y<n;y++)
{
if(!(i>>y&1))
continue;
dp[i][j][x+n]=min(dp[i][j][x+n],dp[i][j^1<<x][y]+dist(y,x+n)/pw[k]);
}
for(int y=0;y<m;y++)
{
if(!(j>>y&1))
continue;
dp[i][j][x+n]=min(dp[i][j][x+n],dp[i][j^1<<x][y+n]+dist(y+n,x+n)/pw[k]);
}
if(i==(1<<n)-1)
ans=min(ans,dp[i][j][x+n]+dist(x+n,n+m)/pw[k+1]);
// printf("%d %d %d %.6lf\n",i,j,x+n,dp[i][j][x+n]) ;
}
}
}
printf("%.10lf",ans);
}