可怜可怜孩子吧,已经调了几个小时了
#include<bits/stdc++.h>
using namespace std;
const int maxn = 20;
const double inf = 1e18;
double dis(int sx, int sy, int ex, int ey){
return sqrt(abs(sx - ex) * abs(sx - ex) + abs(sy - ey) * abs(sy - ey));
}
int n, m;
double x[maxn], y[maxn], speed, ans;
double f[maxn][1<<maxn]; //当前在第i个,城市状态为mask,速度为2^__builtin_popcount(mask>>n)
int main(){
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i = 0; i < n + m; i++) cin >> x[i] >> y[i];
for(int i = 0; i < n + m; i++)
for(int mask = 0; mask < 1 << (n + m); mask++) f[i][mask] = inf;
for(int i = 0; i < n + m; i++) f[i][1<<i] = dis(0, 0, x[i], y[i]);
for(int mask = 1; mask < 1 << (n + m); mask++){
speed = pow(2, __builtin_popcount(mask >> n));
// cout << speed << endl;
for(int i = 0; i < n + m; i++) if((mask >> i) & 1){
for(int j = 0; j < n + m; j++) if(!((mask >> j) & 1)){
f[j][mask^(1<<j)] = fmin(f[j][mask^(1<<j)], f[i][mask] + dis(x[i], y[i], x[j], y[j]) / speed);
}
}
}
ans = inf;
for(int i = 0; i < n + m; i++)
for(int mask = (1 << n) - 1; mask < 1 << (n + m); mask += 1 << n){
speed = pow(2, __builtin_popcount(mask >> n));
ans = fmin(ans, f[i][mask] + dis(0, 0, x[i], y[i]) / speed);
}
cout << fixed << setprecision(10) << ans << endl;
return 0;
}