Aimee

很显然的状压dp

$f_{i,j}$表示在i这个集合，最后停在了j时的最小长度

转移就行了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dis[1301][1301];
int n;
int dp[1<<11][1301];
int main(){

    while(scanf("%d",&n)){
        if(n==0)
        return 0;
        memset(dp,0x3f,sizeof(dp));
        dp[0][0]=0;
        for(int i=0;i<=n;++i){
            for(int j=0;j<=n;++j){
                scanf("%d",&dis[i][j]);
            }
        }
    //  cout<<"1234234";
        for(int k=0;k<=n;++k){
            for(int i=0;i<=n;++i){
                for(int j=0;j<=n;++j){
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
                }
            }
        }
        for(int i=0;i<=(1<<n)-1;++i){
            for(int j=1;j<=n;++j){
                if(i&(1<<(j-1))){
                    for(int k=0;k<=n;++k){
                        if(k==j)
                        continue;
                        if(i&(1<<(k-1))||(k==0&&i-(1<<(j-1))==0)){
                            dp[i][j]=min(dp[i][j],dp[i-(1<<(j-1))][k]+dis[k][j]);
                        //cout<<"sl";
                        }
                    }

                }
            }
        }
        int ans=0x7ffff;
        for(int i=1;i<=n;++i){
            ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]);
        }
        //cout<<dp[(1<<n)-1]
        cout<<ans<<endl;
        //<<endl;
    }
    return 0;
}