这种类型的题很重要，但没有找到OJ，所以主要放一下老师的讲义，以及根据讲义所写的代码。真的遇到这种题能写出来就行了。

描述

N个城市，编号1到N，起点是1，终点是N（N<=16）。

任意两个城市间都有路，A到B和B到A的路可能不一样长。

已知所有路的长度，问经每个城市恰好一次的最短路径的长度。

解法

dp[s][j]表示经过集合s中的每个点恰好一次，且最后走的点是j的最佳路径的长度。

状态转移方程：

dp[s][j] = min { dp[s-j][k] + w[k][j] | k∈s-j }，枚举每一个k，算出最小值

边界条件：

dp[{i}][i] = 0

状态压缩的关键：用short变量表示s，对应位为1表示这个点在这个集合中，对应位为0表示这个点不在这个集合中。

所有点：(1<<n)-1

去掉一个点j：s&(~(1<<j>))或者s-(1<<j)

最终时间复杂度：O(n*n*2^n)

代码如下：由于没有OJ，正确性没有得到验证。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define INF 1<<30
 5 using namespace std;
 6 int w[17][17];//w[i][j]表示从i号城市到j号城市路的长度，变化从0开始
 7 int dp[(1 << 16)][17];
 8 int main() {
 9     int N;
10     cin >> N;
11     memset(dp, 0, sizeof(dp));
12     for (int i = 0; i < N; i++)
13         for (int j = 0; j < N; j++)
14             cin >> w[i][j];
15     for (int j = 0; j < N; j++)
16         dp[1 << j][j] = 0;
17     for (int s = 0; s < 1 << N; s++) {
18         for (int j = 0; j < N; j++) {
19             if ((s >> j) & 1) {//如果j在s集合中
20                 int s_j = s - (1 << j);
21                 if (s_j != 0) {//避免破坏初始设置的边界条件
22                     dp[s][j] = INF;
23                     for (int k = 0; k < N; k++) {//枚举k
24                         if ((s_j >> k) & 1) {
25                             dp[s][j] = min(dp[s][j], dp[s_j][k] + w[k][j]);
26                         }
27                     }
28                 }
29             }
30         }
31     }
32     int result = dp[(1<<N)-1][0];
33     for (int j = 1; j < N; j++)
34         result = min(result, dp[(1 << N) - 1][j]);
35     cout << result << endl;
36     return 0;
37 }