题目描述

$设f[0][1]表示处理到第j个结点,所有结点的访问状态为i.很显然$

$有：f[i][j] = min(f[(i 异或 (1 << j)][k] + a[k][j])$

$注意循环顺序，首先枚举按从小到大状态i,再枚举当前到达的点j,再枚举$

$下一个到达的结点k.并且注意状态是否与当前结点i,k符合.$

$最后的答案就是：f[(1 << n) - 1][n - 1];$

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, f[1 << N][N + 1];
int a[N + 1][N + 1];
int main(){
    memset(f, 0x3f, sizeof(f));
    cin >> n;
    for(int i = 0;i < n;i ++)
        for(int j = 0;j < n;j ++)
            cin >> a[i][j];
    f[1][0] = 0;
    for(int i = 1;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] + a[k][j]);
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}