Hie with the Pie（POJ 3311状压dp）

题意：披萨店给n个地方送披萨，已知各地方（包括披萨店）之间花费的时间，求送完所有地方并回到店花费的最小时间

分析：状态好确定dp[i][j],i中1表示地方已送过，否则为0，j为当前状态最后一个送过的地方，注意怎么走才算最小时间，当然是走最短路，点很少由floyd求出各点最短路

求回到店的最小时间，从店出发（状态为1）。

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  1000000007;

int d[15][15],a[15][15],n,dp[2500][15];

void solve(){

    int c=(1<<(n+1))-1;

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

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

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

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

    memset(dp,-1,sizeof(dp));

    dp[1][0]=0;

    for(int i=1;i<=c;++i){

        i|=1;

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

        if(dp[i][j]==-1)continue;

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

            if(dp[i|(1<<k)][k]==-1&&j!=k||dp[i|(1<<k)][k]>dp[i][j]+d[j][k])

            dp[i|(1<<k)][k]=dp[i][j]+d[j][k];

    }

    }

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

}

int main()

{

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

            if(n==0)break;

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

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

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

        solve();

    }

return 0;

}