치즈를 먹다-dp상압

P1433은 치즈 dfs 템플릿 문제를 먹습니다. 상압을 연습하는 데 쓰겠습니다.

#include
using namespace std;
double dp[100000][20];
double x[20],y[20];
double dis[20][20];
int n;
double getdis(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]) );
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf%lf",&x[i],&y[i]);
    }
    x[0]=y[0]=0;
    for(int i=0;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            dis[i][j]=getdis(i,j);
            dis[j][i]=dis[i][j];
        }
    }
    fill(dp[0],dp[0]+100000*20,10000000);
//    cout<
    dp[0][0]=0;
    for(int i=1;i<=n;++i){
        dp[(1<<(i-1))][i]=dis[i][0];
    }
    for(int i=1;i<=(1<<n)-1;++i){
        for(int j=1;j<=n;++j){
            if(i&(1<<(j-1))){
                for(int k=1;k<=n;++k){
                    if(k==j) continue;
                    if( (i^(1<<(j-1)))&(1<<(k-1))){
                        dp[i][j]=min(dp[(i^(1<<(j-1)))][k]+dis[j][k],dp[i][j] );
                    }
                }
            }
        }
    }
    double Min=100000000;
    for(int i=1;i<=n;++i){
        Min=min(dp[((1<<n)-1)][i],Min);
    }
    printf("%.2lf",Min);
    return 0;
}