$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

$n$ 很小，所以考虑状压。

设 $f_{i,S}$ 表示最后停在 $i$ 这个点，经过的点集合为 $S$ 的最短路径长度。
初始状态 $f_{0,1}=0$，答案 $f_{n-1,2^n-1}$。

考虑转移，枚举 $S,i$，再枚举上一次从 $k$ 过来。时间复杂度 $O(2^n \times n^2)$，由于时限 $5s$，可以通过。

#include <bits/stdc++.h>
using namespace std;
const int N = 25, M = (1 << 20) + 15;
int n, w[N][N];
int dp[N][M];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);
    memset(dp, 0x3f3f3f3f, sizeof dp);
    dp[0][1] = 0;   //起点是 0
    for (int S = 0; S < (1 << n); S++) {
        for (int i = 0; i < n; i++) {
            if ((S & (1 << i)) == 0) continue;
            for (int j = 0; j < n; j++) {
                int S2 = (S ^ (1 << i));
                if (S2 & (1 << j))
                    dp[i][S] = min(dp[i][S], dp[j][S2] + w[i][j]);
            }
        }
    }
    printf("%d\n", dp[n - 1][(1 << n) - 1]);
    return 0;
}