P1433 50分求调

#include <bits/stdc++.h>
using namespace std;
double dp[1000][1000];
double x[20];
double y[20];
double length_ch(double  a,double b,double c,double d){
    return sqrt((a-b)*(a-b)+(c-d)*(c-d));
}
int n;
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    memset(dp,127,sizeof(dp));  
	for(int s=1;s<(1<<n);s++) 
        for(int i=1;i<=n;i++)
        {
            if((s&(1<<(i-1)))==0){
                continue;
            }
            if(s==(1<<(i-1))) {
                dp[i][s]=0;
                continue;
            }
            for(int j=1;j<=n;j++)
            {
                if((s&(1<<(j-1)))==0||i==j){
                	continue;
				}
                dp[i][s] = min(dp[i][s],dp[j][s-(1<<(i-1))]+length_ch(x[i],x[j],y[i],y[j]));
            }
        }
        double ans=-1;
        for(int i=1;i<=n;i++){ 
            double s=dp[i][(1<<n)-1]+length_ch(x[i],x[0],y[i],y[0]);
            if(ans==-1||ans>s) ans=s;
        }
        printf("%.2lf\n",ans); 
    return 0;
}