这一题的 BF 解法: 枚举点的全排列取最短, 状态数量 $\mathcal O(n!\cdot n)$ . $n = 20$, 时限 5s, 过不了.

考虑状态定义, 需要记录:

1. 走过哪些点;
2. 当前处于哪一个点.

考虑状压 DP . 即将 0/1 状态压缩到一个整数中, 使得可以通过状态调用子问题答案.

设 $f_{st, u}$ 为当前走到 $u$ 号点, 走过与否的局面为 0/1 集合 $ st $ .

则: $ f_{st, u} = \min _ {0 \le v \le n - 1} ( f_ {st_v, v} + dis_ {u, v} ) $.
其中 $st_v$ 为 $st$ 除去 $u$ 得到的状态集合. 可以使用位运算 st ^ (1 << u) 得到.

现在枚举 $st$ ([0, (1 << n) - 1], 即全 $0$ 到全 $1$)、点$u, v$, 即可. 注意状态是否合法(代码中 if 语句).

#include <iostream>
#include <cstring>
using namespace std;
const int N = 28;
int dis[N][N], n, f[1 << 20][20];
int main() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cin >> dis[i][j];
        }
    }
    memset(f, 0x3f, sizeof f); f[1][0] = 0;
    for(int st = 0; st <= (1 << n) - 1; ++st) {
        for(int u = 0; u < n; ++u) {
            if(st >> u & 1) {
                for(int v = 0; v < n; ++v) {
                    // 获取 0/1 状态集合 st 中除去 u 的状态集合: st ^ (1 << u)
                    // 也可以这么写: st - (1 << u)
                    if(st ^ (1 << u) >> v & 1) f[st][u] = min(f[st][u], f[st ^ (1 << u)][v] + dis[u][v]);   
                }
            }
        }
    }
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}