【算法】状态压缩型动态规划
【题解】http://blog.csdn.net/harryguo2012/article/details/42175559（初始不算经过起点1的话，答案就是f[1][(1<<n)-1]）
先跑一遍floyd后就不用再纠结重复经过的问题了！！！
然后就转化为经典状压问题。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=20; int n,mp[maxn][maxn],f[maxn][70010]; int main() { scanf("%d",&n);n++; int x; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&x); mp[i][j]=x; } } for(int i=1;i<=n;i++)mp[i][i]=0; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]); memset(f,0x3f,sizeof(f)); f[1][0]=0; for(int k=1;k<=(1<<n)-1;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((1<<(i-1))&k)f[i][k]=min(f[i][k],f[j][k-(1<<(i-1))]+mp[j][i]); printf("%d",f[1][(1<<n)-1]); return 0; }
原文：http://www.cnblogs.com/onioncyc/p/6505203.html
