$TSP$是一个“组合优化问题”，同时也是数学领域中一个较为著名的$NPC$问题。
现在的算法都没有办法在确定型机器上在多项式时间内求出最优解，但是有办法在多项式时间内求出一个较优解。
可以发现这个问题并不是真正意义上的$NPC$，而是属于一个$NP-Hard$，因此可以求出较优解。
这个问题的实质就是求一个带权无向图中，找一个权值最小的哈密尔顿回路，在给出的节点数目非常小的情况下，我们可以考虑状压$DP$。
当然，我们知道没有什么算法是暴力搜索解决不了的，在没有十分优的解决方案的时候没我们自然想到枚举全排列。
但是这显然白搭，因为$O(N!)$的时间复杂度即使点数很小也是很难接受的。
于是考虑压缩状态。对于一种方案，我们用一个$N$位的二进制数表示，其中$1$表示第$i$个点被经过，若是$0$则是没有经过。
我们设$Dp[i][j]$表示路径状态为$i$，当前处于$j$节点的最短路径。
假设我们现在有一个$Dp[i][j]$，那么我们可以枚举一个点$k$，因为当前的$j$是刚刚经过，因此上一个状态一定没有经过$j$这个点。因此在上一个时刻的点的状态的第$j$位就一定是$0$，状态就是$i \times (1 << k)$。
并且从$k$走到$j$需要$L[i][j]$（也就是两点之间的最短路），于是我们取遍所有的$k$取最小值即可。
得出递推关系式：
目标的状态显然是$Dp[(1 << N) - 1][N - 1]$（因为起点是$0$）。
以上需要用到不少的位运算，如果不是很懂的还请去学学为好。
下面给出的是$1 \leq N \leq 20$的数据，$L[i][j]$是两个点之间的距离。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using namespace std ;
typedef long long LL ;
const int MAXN = 21 ;
const int MAXM = 21 ;
int N, Dp[1 << 20][MAXN], L[MAXN][MAXN], Ans = 10000000 ;
inline int Read() {
int X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
inline int Min(int A, int B) {return (A < B) ? A : B ;}
int main() {
N = Read() ;
memset(Dp, 127, sizeof(Dp)) ;
Dp[1][0] = 0 ;
for (int i = 0 ; i < N ; i ++)
for (int j = 0 ; j < N ; j ++)
L[i][j] = Read() ;
for (int i = 1 ; i < (1 << N) ; i += 2)
for (int j = 0 ; j < N ; j ++)
if ((i >> j) & 1)
for (int k = 0 ; k < N ; k ++) {
if (j == k || !((i >> k) & 1)) continue ;
Dp[i][j] = Min(Dp[i][j], Dp[i ^ (1 << j)][k] + L[k][j]) ;
}
for (int i = 0 ; i < N ; i ++)
Ans = Min(Ans, Dp[(1 << N) - 1][i] + L[i][0]) ;
printf("%d\n", Ans) ; return 0 ;
}