poj3311 TSP经典状压dp(Traveling Saleman Problem)

题目链接：http://poj.org/problem?id=3311

题意：一个人到一些地方送披萨，要求找到一条路径能够遍历每一个城市后返回出发点，并且路径距离最短。最后输出最短距离即可。注意：每一个地方可重复访问多次。

经典的状压dp，因为每次送外卖不超过10个地方，可以压缩。

由于题中明确说了两个城市间的直接可达路径（即不经过其它城市结点）不一定是最短路径，所以需要借助floyd首先求出任意两个城市间的最短距离。

然后，在此基础上来求出遍历各个城市后回到出发点的最短路径的距离，即求解TSP问题。

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define ll long long

const int maxn=1e5+;

const int INF=0x3f3f3f3f;

int dp[<<][];

int d[][];

int n;

void floyd()  ///多源最短路，任意两点之间的距离都是最短的

{

    for(int k=; k<=n; k++)

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

    for(int j=; j<=n; j++)

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

}

///dp[i][j]表示已经走过的城市为i，当前所在的城市为j的最短路程。

///相应的状态转移方程为dp[i][j]=min(dp[i^(1<<j)][k]+d[k][j]);

///i^(1<<j)的意思是将j这个城市从i状态中去掉。 d[k][j] 是k和j之间的距离。

void DP()

{

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

    for(int j=; j<=n; j++)

    {

        int tmp=<<(j-);

        if(tmp==i) dp[i][j]=d[][j];

        else if(tmp&i)

        {

            dp[i][j]=INF;

            for(int k=; k<=n; k++)

                if(k!=j && (i&(<<(k-))))

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

        }

    }

    int x=(<<n)-;

    int ans=INF;

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

        ans=min(ans,dp[x][i]+d[i][]);

    printf("%d\n",ans);

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(scanf("%d",&n)== && n)

    {

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

        for(int j=; j<=n; j++)

        scanf("%d",&d[i][j]);

        floyd();

        DP();

    }

    return ;

}

poj3311 TSP经典状压dp(Traveling Saleman Problem)的相关教程结束。