题目地址：

pid=5067">HDU 5067

经典的TSP旅行商问题模型。

状压DP。

先分别预处理出来每两个石子堆的距离。然后将题目转化成10个城市每一个城市至少经过一次的最短时间模型。然后简单的状压DP就可以。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

#define LL __int64

const int INF=0x3f3f3f3f;

int d[20][20], dp[1<<12][12];

struct node

{

    int x, y;

} stone[20];

int main()

{

    int n, m, i, j, x, cnt, y, tmp, k;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        cnt=0;

        stone[0].x=stone[0].y=0;

        for(i=0; i<n; i++)

        {

            for(j=0; j<m; j++)

            {

                scanf("%d",&x);

                if(x)

                {

                    stone[++cnt].x=i;

                    stone[cnt].y=j;

                }

            }

        }

        for(i=0; i<=cnt; i++)

        {

            for(j=0; j<=i; j++)

            {

                x=abs(stone[i].x-stone[j].x)+abs(stone[i].y-stone[j].y);

                d[i][j]=d[j][i]=x;

            }

        }

        /*for(i=0;i<=cnt;i++)

        {

            for(j=0;j<=cnt;j++)

            {

                printf("%d ",d[i][j]);

            }

            puts("");

        }*/

        memset(dp,INF,sizeof(dp));

        y=1<<cnt;

        dp[y-1][0]=0;

        //printf("%d\n",y);

        for(i=y-1; i>=0; i--)

        {

            for(j=0; j<cnt; j++)

            {

                if(i&(1<<j))

                {

                    tmp=i-(1<<j);

                    if(i==y-1)

                    {

                        dp[tmp][j+1]=dp[i][0]+d[0][j+1];

                        continue ;

                    }

                    for(k=1;k<=cnt;k++)

                    {

                        if(dp[i][k]!=INF)

                        {

                            dp[tmp][j+1]=min(dp[tmp][j+1],dp[i][k]+d[k][j+1]);

                        }

                    }

                }

            }

        }

        int min1=INF;

        for(i=1;i<=cnt;i++)

        {

            dp[0][i]+=d[0][i];

            min1=min(min1,dp[0][i]);

        }

        printf("%d\n",min1==INF?

0:min1);

    }

    return 0;

}