经典状压DP，以后还是要多练习练习。
设 \(f[i][j]\) 表示 \(i\) 状态 ， 最后一个点落在 \(j\) 点的最短路径。
记住，i是一个状态，是二进制的状态压缩。
那么我们来推推公式，推出来后是这个样子：
\[f[i][j]=\text{min }\{ f[i\text{ xor }(1<<j)][k]+dis[k][j] \}\]
我们设\(k\)是上一个节点，转移到\(j\)节点。
xor是异或 ，i xor (1<<j)表示 i 状态二进制下第 j 位取反。我们当做这个状态下还没有来过 j 节点，现在在k节点
理解了f[ ]数组的意思，我们发现：\(i\) 状态下必须有 \(j\)节点，或者说\(i\)状态的二进制下第 \(j\) 位是1，同理，k也是。 所以我们还要判断一下 \(i\) 状态下是否有 \(j\) , \(i\) 无 \(j\) 的状态下是否有 \(k\)。
说得不好，挂一下代码吧。
Code
#include<bits/stdc++.h> #define N 27 #define MAXN 1<<20 using namespace std; int n; int dis[N][N],f[MAXN][N]; int main() { scanf("%d",&n); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&dis[i][j]); int maxn = (1<<n)-1; memset(f,0x3f,sizeof(f)); f[1][1] = 0; //000...01状态 1号点 for(int i=2;i<=maxn;++i) { for(int j=1;j<=n;++j) if((i>>(j-1)) & 1) for(int k=1;k<=n;++k) if((i^(1<<(j-1)))>>(k-1) & 1) f[i][j] = min(f[i][j],f[i^(1<<(j-1))][k]+dis[k][j]); } printf("%d\n",f[maxn][n]); return 0; }转载于:https://www.cnblogs.com/BaseAI/p/11406664.html
相关资源：JAVA上百实例源码以及开源项目