做题感悟：在比赛的时候SB了，明明是个很裸的TSP但是第二组样例一直不对，很是无语，最后发现数组开倒了
。
解题思路：
这题应该属于TSP入门题。状态方程： dp [ S|( 1 << j) ] [ i ] = min ( dp [ S ] [ i ] + d [ i ] [ j ] ) ;
代表达到状态 S|(1<<j) ,到达 j 点所形成的最优状态，等于达到状态 S ,到达 i 点，然后再从 i 点到 j 点的距离。不断更新就好。
代码：
#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define INT __int64
#define L(x) (x * 2)
#define R(x) (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const INT mod = 10000007 ;
const int MY = 1400 + 5 ;
const int MX = (1<<12) + 5 ;
int n ,m ,num ;
int dp[MX][25] ,d[25][25] ;
struct node
{
int x ,y ;
}P[50] ;
void DP_SC()
{
memset(dp ,INF ,sizeof(dp)) ;
dp[1][0] = 0 ;
for(int S = 0 ;S < (1<<num) ; ++S)
for(int i = 0 ;i < num ; ++i)
if(dp[S][i] != INF)
{
for(int j = 0 ;j < num ; ++j)
{
if(S&(1<<j)) continue ;
dp[S|(1<<j)][j] = min(dp[S|(1<<j)][j] ,dp[S][i] + d[i][j]) ;
}
}
int S = (1<<num)-1 ,ans = INF ;
for(int i = 0 ;i < num ; ++i)
ans = min(ans ,dp[S][i] + d[i][0]) ;
cout<<ans<<endl ;
}
int main()
{
//freopen("input.txt" ,"r" ,stdin) ;
while(~scanf("%d%d" ,&n ,&m))
{
num = 1 ;
int x ;
for(int i = 0 ;i < n ; ++i)
for(int j = 0 ;j < m ; ++j)
{
scanf("%d" ,&x) ;
if(x&&(i+j))
{
P[num].x = i ;
P[num++].y = j ;
}
}
P[0].x = 0 ;
P[0].y = 0 ;
for(int i = 0 ;i < num ; ++i)
for(int j = 0 ;j < num ; ++j)
d[i][j] = abs(P[i].x-P[j].x) + abs(P[i].y-P[j].y) ;
DP_SC() ;
}
return 0 ;
}