贴一个TSP讲解：点击打开链接

错误的转移方程

dp[i][j] 把i当作了步数，以为至多走N步就可以了。作死啊

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 1100
#define inf 0x3f3f3f3f
const double eps=1e-8;
using namespace std;
int dp[12][1<<12];
int maps[12][12];
int path[12][12];
int dict[12][12];
int n,m;
int BitCnt( int n)
{
    int value = http://www.mamicode.com/0;>
ACCEPT
正确的方程是dp[i][j]  在状态i下，以j为结尾的最短路径。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 1100
#define inf 0x3f3f3f3f
const double eps=1e-8;
using namespace std;
int dp[1<<12][12];
int maps[12][12];
int n,m;

void ford()
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
                if(maps[i][j]>maps[i][k]+maps[k][j])
                    maps[i][j]=maps[i][k]+maps[k][j];

}
int main()
{
  //  freopen("in.txt","r",stdin);
    while(~scanf("%d",&n) && n)
    {

        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
                scanf("%d",maps[i]+j);
        int rt=(1<<n+1)-1;
        ford();memset(dp,0x3f,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=rt;i++)
            for(int j=0;j<=n;j++)
            {
                if( ( i&(1<<j ) )==0) continue;//没有这个点就不转移了
                if( i == (1<<j) ){dp[i][j]=maps[0][j];break;}//就一个点那就是直接去最短
                for(int k=0;k<=n;k++)
                {
                    if( (i&  (1<<k) ) && k!=j )
                        dp[i][j]=min( dp[i][j],dp[i& ~ (1<<j)][k]+maps[k][j]   );//k不是j点且i中有这个点
                }
            }
        int ans=inf;
        for(int i=1;i<=n;i++)
            ans=min(ans, dp[rt][i]+maps[i][0]);
        printf("%d\n",ans);

    }
    return 0;
}
//贴一个他人的注释
//Floyd + 状态压缩DP  
//题意是有N个城市(1~N)和一个PIZZA店(0),要求一条回路，从0出发，又回到0，而且距离最短  
//也就是TSP(旅行商)问题，首先不难想到用FLOYD先求出任意2点的距离dis[i][j]  
//接着枚举所有状态，用11位二进制表示10个城市和pizza店，1表示经过，0表示没有经过  
//定义状态DP(S,i)表示在S状态下，到达城市I的最优值  
//接着状态转移方程:DP(S,i) = min{DP(S^(1<<i-1),k) + dis[k][j],DP(S,i)},器重S^(1<<i-1)表示未到达城市i的所有状态，1<=k<=n  
//对于全1的状态，即S = (1<<n)-1则表示经过所有城市的状态，最终还需要回到PIZZA店0  
//那么最终答案就是min{DP(S,i) + dis[i][0]}  


POJ 3311 Hie with the Pie(Floyd+状态压缩DP)