这种类型的题很重要，但没有找到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 }