题解 | dd爱探险

因为很小，只有最多16，所以考虑状压dp，代表当前已经访问了mask中二进制已经为1的空间站并且目前在第k个空间站的最小代价，分别代表当前已经访问了mask中二进制已经为1的空间站并且目前在第k个空间站的过程中最大的代价跟最小的代价，因为我们要将一次代价变成，一次代价翻倍，那么就相当于把最大的变成，把最小的多算一次，转移的时候分类讨论一下

时间复杂度是

void solve(){
    int n;
    cin>>n;
    vector<vector<int>> dp(1<<n,vector<int>(n+1,0));
    vector<vector<int>> dmx(1<<n,vector<int>(n+1,-1));
    vector<vector<int>> dmi(1<<n,vector<int>(n+1,1e9));
    int c[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>c[i][j];
        }
    }
    int mask=1<<n;
    for(int i=0;i<mask;i++){
        int cnt=__builtin_popcount(i);
        if(cnt>=4){
            for(int j=0;j<n;j++){
                if(i>>j&1){
                    int res=1e9;
                    int mxf=1e9,mif=0;
                    for(int k=0;k<n;k++){
                        if((i>>k&1)&&j!=k){
                            if(c[k][j]>dmx[i^(1<<j)][k]){
                                if(res>dp[i^(1<<j)][k]+dmx[i^(1<<j)][k]){
                                    res=dp[i^(1<<j)][k]+dmx[i^(1<<j)][k];
                                    mxf=c[k][j];
                                    mif=dmi[i^(1<<j)][k];
                                }
                            }
                            else if(c[k][j]<dmi[i^(1<<j)][k]){
                                if(res>dp[i^(1<<j)][k]-dmi[i^(1<<j)][k]+2*c[k][j]){
                                    res=dp[i^(1<<j)][k]-dmi[i^(1<<j)][k]+2*c[k][j];
                                    mxf=dmx[i^(1<<j)][k];
                                    mif=c[k][j];
                                }
                            }else{
                                if(res>dp[i^(1<<j)][k]+c[k][j]){
                                    res=dp[i^(1<<j)][k]+c[k][j];
                                    mxf=dmx[i^(1<<j)][k];
                                    mif=dmi[i^(1<<j)][k];
                                }
                            }
                        }
                    }
                    dp[i][j]=res;
                    dmx[i][j]=mxf;
                    dmi[i][j]=mif;
                }
            }
        }else{
            if(cnt==2){
                for(int j=0;j<n;j++){
                    if(i>>j&1){
                        for(int k=0;k<n;k++){
                            if((i>>k&1)&&j!=k){
                                dmx[i][k]=c[j][k];dmi[i][k]=c[j][k];
                                dmx[i][j]=c[k][j];dmi[i][j]=c[k][j];
                            }
                        }
                    }
                }
            }else if(cnt==3){
                for(int j=0;j<n;j++){
                    if(i>>j&1){
                        for(int k=0;k<n;k++){
                            if((i>>k&1)&&j!=k){
                                dmx[i][j]=max(dmx[i^(1<<j)][k],c[k][j]);
                                dmi[i][j]=min(dmi[i^(1<<j)][k],c[k][j]);
                            }
                        }
                        dp[i][j]=2*dmi[i][j];
                    }
                }
            }
        }
    }
    int ans=1e9;
    for(int i=0;i<n;i++){
        ans=min(dp[mask-1][i],ans);
    }cout<<ans;
}