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[15][15],dp[2500][15];
/// dp[状态][当前点]=路径长度，G[i][j]= i 到 j 的最短路长度  
/// 状态 即当该数的二进制为01011时，说明0 1 3点已走过，而2 4没有
void solve()
{
    int ed=(1<<(n+1))-1;
    /// ed的二进制表示所有点都走过
    /* 如 当n=3
    1(00001)<<(n+1)=16(10000)
    16(10000)-1=15(01111)*/
    
    memset(dp,INF,sizeof(dp));// INF表示不存在
    dp[1][0]=0;/// 一开始已经在0点，0点为pizza店
    for(int i=1;i<=ed;i++)
    {
        if(!(i&1)) continue;
        /// 取0点已走过的状态 0点没走过的状态不用考虑
        
        for(int j=0;j<=n;j++)
        {// 若目前不存在 i状态时位于j点的可能 则忽略
            if(dp[i][j]==INF) continue; // 不存在
            
            for(int k=0;k<=n;k++)  // 枚举所有点
            /// 从 i 状态延伸到 k 点已走过的状态
                if(j!=k) dp[i|(1<<k)][k]= // 则更新
                min(dp[i|(1<<k)][k],dp[i][j]+G[j][k]);
        }
    }
    printf("%d
",dp[ed][0]);
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++)
                scanf("%d",&G[i][j]);
        for(int i=0;i<=n;i++) /// floyd更新G[][],求各点间的最短路
            for(int j=0;j<=n;j++)
                for(int k=0;k<=n;k++)
                    if(G[j][k]>G[j][i]+G[i][k])
                        G[j][k]=G[j][i]+G[i][k];
        solve();
    }
    return 0;
}