East Central North America 2006 Hie with the Pie /// 状压dp oj22470

题目大意：

输入n，有n个地方(1~n）需要送pizza

pizza点为0点

接下来n+1行每行n+1个值

表示 i 到 j 的路径长度

输出从0点到各点送pizza最后回到0点的最短路（点可重复走）

Sample Input

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0

Sample Output

8

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

int n,G[][],dp[][];

/// dp[状态][当前点]=路径长度，G[i][j]= i 到 j 的最短路长度

/// 状态 即当该数的二进制为01011时，说明0 1 3点已走过，而2 4没有

void solve()

{

    int ed=(<<(n+))-;

    /// ed的二进制表示所有点都走过

    /* 如 当n=3

    1(00001)<<(n+1)=16(10000)

    16(10000)-1=15(01111)*/

    memset(dp,INF,sizeof(dp));// INF表示不存在

    dp[][]=;/// 一开始已经在0点，0点为pizza店

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

    {

        if(!(i&)) continue;

        /// 取0点已走过的状态 0点没走过的状态不用考虑

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

        {// 若目前不存在 i状态时位于j点的可能 则忽略

            if(dp[i][j]==INF) continue; // 不存在

            for(int k=;k<=n;k++)  // 枚举所有点

            /// 从 i 状态延伸到 k 点已走过的状态

                if(j!=k) dp[i|(<<k)][k]= // 则更新

                min(dp[i|(<<k)][k],dp[i][j]+G[j][k]);

        }

    }

    printf("%d\n",dp[ed][]);

}

int main()

{

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

    {

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

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

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

        for(int i=;i<=n;i++) /// floyd更新G[][],求各点间的最短路

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

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

                    if(G[j][k]>G[j][i]+G[i][k])

                        G[j][k]=G[j][i]+G[i][k];

        solve();

    }

    return ;

}