类似题求方案数 - 2021第十二届蓝桥杯大赛软件赛省赛C++大学A组 – 试题 E: 回路计数

N 最多开到20，21就不行了

/*
    f[i][j] : 经过路径是i，且停留在j的花费
        属性：最小值 
        ans: f[(1 << n) - 1][j] + w[j][0] , f[1][0] = 0;
        对比 91. 最短Hamilton路径,答案 还需要回到原点

    f[i][j] = f[i - {j}][k] + w[k][j];
*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20, M = 1 << N;

int n;
int w[N][N];
int f[M][N];

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++ )
        for(int j = 0;j < n;j ++ )
            cin >> w[i][j];

    memset(f,0x3f,sizeof f);
    f[1][0] = 0;

    for(int i = 0;i < (1 << n) ;i ++ )
    {
        for(int j = 0;j < n;j ++ )
            if(i >> j & 1)
                for(int k = 0;k < n;k ++ )
                    if( (i - (1 << j)) >> k & 1) 
                        f[i][j] = min(f[i][j],f[i - (1 << j)][k] + w[k][j]);
    }

    // 枚举所有到达出发点前一个城市的状态并取最小值
    int ans = 0x3f3f3f3f;
    for(int i = 1;i < n;i ++ )
        ans = min(ans, f[(1 << n) - 1][i] + w[i][0]); 

    cout << ans << endl;

    return 0;
}