P1433 吃奶酪 (TSP)

Link

#include <bits/stdc++.h>
# define LL long
using namespace std;

const int INF=0x7fffffff;
int n;
double x[16];
double y[16];
double dp[17][1<<16];

double dfs(int u, int m){
    if(m==0) return 0;
    if(dp[u][m]!=-1.0) return dp[u][m];
    double res=10000000.0;
    for(int i=0;i<=n;++i){
        if((m&(1<<i))>0){
            double dis=sqrt((x[u]-x[i])*(x[u]-x[i])+(y[u]-y[i])*(y[u]-y[i]));
            res=min(res,dis+dfs(i,m^(1<<i)));
        }
    }
    return dp[u][m]= res;
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;++i){
        cin>>x[i]>>y[i];
    }
    x[0]=y[0]=0;
    for(int i=0;i<=n;++i){
        for(int j=0;j<(1<<(n+1));++j){
            dp[i][j]=-1.0;
        }
    }
    double res=dfs(0,((1<<(n+1))-1)^1 );
    printf("%.2f", res);
    return 0;
}