一. 题目

二. 思路

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=25, M=(1<<20)+10, INF=2e9;

int n;
int g[N][N];

class DP
{
public:
    int f[M][N];
public:
    DP()
    {
        initIO();
        fill(f[0], f[0]+N*M, INF);
        f[1][0]=0;//在0起点，且状态为1，表示走过0，距离0
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    int work()
    {
        for(int j=0;j<(1<<n);++j)//枚举当前状态
            for(int i=0;i<n;++i)//枚举当前位置
                if(j>>i&1)//判断当前状态是否含当前位置
                    for(int k=0;k<n;++k)//枚举上一个城市
                        if((j-(1<<i))>>k&1)//去掉当前城市，仍含K
                            f[j][i]=min(f[j][i], f[j-(1<<i)][k]+g[k][i]);
        return f[(1<<n)-1][n-1];
    }
}dp;

int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            cin>>g[i][j];
    cout<<dp.work();
}