题解 | dd爱探险

好难

#include<bits/stdc++.h>
using namespace std;
#define int long long
int p[20][20];
int dp[1<<16][16][2][2];//mask,u,g,r
const int INF = 0x3f3f3f3f3f3f3f3f;
void solve(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>p[i][j];
        }
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<n;i++) dp[1<<i][i][0][0]=0;
    for(int mask=1;mask<(1<<n);mask++){
        for(int u=0;u<n;u++){
            if(!(mask&(1<<u))) continue;
            for(int g=0;g<=1;g++){
                for(int a=0;a<=1;a++){
                    if(dp[mask][u][g][a]==INF) continue;
                    for(int v=0;v<n;v++){
                        if(mask&(1<<v)) continue;
                        int newmask=mask|(1<<v);
                        dp[newmask][v][g][a]=min(dp[newmask][v][g][a],dp[mask][u][g][a]+p[u][v]);
                        if(!g) dp[newmask][v][1][a]=min(dp[newmask][v][1][a],dp[mask][u][g][a]);
                        if(!a) dp[newmask][v][g][1]=min(dp[newmask][v][g][1],dp[mask][u][g][a]+2*p[u][v]);
                }
                }
            }
        }
    }
    int ans=INF;
    for(int i=0;i<n;i++) ans=min(ans,dp[(1<<n)-1][i][1][1]);
    cout<<ans;
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}