POJ 3311 Hie with the Pie（floyd/状压dp）

POJ 3311 Hie with the Pie（floyd/状压dp）

题目大意

​ 一个人要送n份货，给出一个矩阵，表示任意两个点间的直接路径的时间，求从起点0送完这n份货（到达指定的n个地点）再回到起点0的最短时间

input

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

output

8

分析

我们可以先计算出点之间的最短路，再枚举到达一个点时所有经过了的点的状态，然后枚举中间点

用一个二进制数 i 表示状态，0为没经过这个点，1经过了这个点。

dp_{i j} 表示当前状态为i，最后到达的一个点是j的最小路程，dis_{i j}是i j两点间最短路

枚举到达 j 时经过的点所有可能的状态，把a的第j位取反，枚举中间点k。

dp[i][j] = min(dp[i][j], dp[i^(1<<(j-1))][k]+dis[k][j])

写了很多注释，可能更详细一点吧，，，

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int INF = 0x7fffffff;
int dp[1<<11][11], dis[11][11], n;//dp[i][j]表示当前状态为i，最后到达的一个点是j的最小路程，dis[i][j]是两点间最短路
int main(){
    while(scanf("%d", &n)!=EOF && n){
        for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) scanf("%d", &dis[i][j]);
        for(int k=0; k<=n; k++)
            for(int i=0; i<=n; i++)
                for(int j=0; j<=n; j++)
                    if(dis[i][j] > dis[i][k]+dis[k][j]) dis[i][j] = dis[i][k]+dis[k][j];//floyd算出任意两点间最短路，不多说
        for(int i=0; i<(1<<n); i++){ // 枚举状态i
            for(int j=1; j<=n; j++){//枚举状态i下到达的城市j
                if(i == (1<<(j-1))) dp[i][j] = dis[0][j];//此时只到达了 j
                else{
                    dp[i][j] = INF;//初始化最大值
                    for(int k=1; k<=n; k++)//先到k，再到j
                        if((k != j) && (i & (1 << (k-1))))  dp[i][j] = min(dp[i][j], dp[i^(1<<(j-1))][k]+dis[k][j]);//k和j不能相同，且状态i下到过k
                        //如果状态i到j，把那一位变成0，表示从一个不到j且最后到达的点是k的状态的最短路程，再加上k到j的最短路程
                        //如果状态i没到过j，右边的式子就是从一个到过了j且最后到达的是k状态，又从k回到j，肯定不是最短的
                }
            }  
        }
        int ans = dp[(1 << n) - 1][1] + dis[1][0];
            for(int i=2; i<=n; i++) ans = min(ans, dp[(1 << n) - 1][i] + dis[i][0]);//枚举中间点并计算最短路程
            printf("%d
", ans);
    }
    return 0;
}