为什么只有90??
直接气炸了
#include<bits/stdc++.h>
using namespace std;
using db = double;
int n;
db x[16], y[16], dp[16][(1 << 15)], ans = 1e9;
db dis(int a, int b){
return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= (1 << n); j++){
dp[i][j] = 1e9;
}
}
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
dp[i][1 << (i - 1)] = dis(i, 0);
}
for(int i = 1; i < (1 << n); i++){
for(int j = 1; j <= n; j++){
if((i & (1 << (j - 1))) == 0) continue;
for(int k = 1; k <= n; k++){
if(j == k || (i & (1 << (k - 1))) == 0) continue;
dp[j][i] = min(dp[j][i], dp[k][i - (1 << (j - 1))] + dis(j, k));
}
}
}
for(int i = 1; i <= n; i++) ans = min(ans, dp[i][(1 << n) - 1]);
cout << fixed << setprecision(2) << ans;
return 0;
}