http://acm.hdu.edu.cn/showproblem.php?pid=5067

 思路：问题可以转化成：从某一点出发，遍历网格上的一些点，每个点至少访问一次需要的最小时间是多少。这就是经典的旅行商问题，考虑到我们必须要遍历的点只有不到10个，可以用状态压缩解决。

dp[i][j]表示i状态的点被访问过了，当前停留在点j 需要的最少时间,状态转移方程：dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+abs(q[j].x-q[k].x)+abs(q[j].y-q[k].y));

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 const int inf=1<<30; 7  8 int n,m; 9 int g[100][100];10 int dp[1<<11][100];11 struct node12 {13     int x,y;14 }st;15 16 int main()17 {18      while(scanf("%d%d",&n,&m)!=EOF)19      {20          vector
          
           q;21          for(int i=1; i<=n; i++)22          {23              for(int j=1; j<=m; j++)24              {25                  scanf("%d",&g[i][j]);26                  if(i==1&&j==1)27                  {28                      st.x=i;29                      st.y=j;30                      q.push_back(st);31                  }32                  else if(g[i][j])33                  {34                      st.x=i;35                      st.y=j;36                      q.push_back(st);37                  }38              }39          }40          int x=q.size();41          for(int i=0; i<(1<
          
         
        
       
      

 

Dp[i|(1≪k)][k]=min(Dp[i|(1≪k)][k],Dp[i][j]+Dis(j,k))