题目：Hie with the Pie
题意：从0出发，走n个城市，最后回到0点，求最少花费
分析：状态压缩：dp[i][j]表示在i状态下，当前遍历第j个点的最小值
初始化：dp[1<<i][i] = d[0][i]
状态转移：dp[i][j] = min(dp[s][k] + d[k][j]) 其中s是i的子状态,在状态i的基础上,第j位为0的状态
d[k][j]是从k走到j的最小花费，用floyd预处理出所有的d[u][v]
代码：
#define mem(a,x) memset(a,x,sizeof(a)) #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; /* dp[i][j]表示在i状态下，当前遍历第j个点的最小值 初始化： dp[1<<i][i] = d[0][i] 状态转移： dp[i][j] = min(dp[s][k] + d[k][j]) 其中s是i的子状态,在状态i的基础上,第j位为0的状态 例如：01100 -> 01110 j j 01100算是01110的子状态，从k走到j花费d[k][j] */ int dp[1<<12][12]; int d[12][12]; const int inf = 0x3f3f3f3f; void floyd(int n) { 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]); } } } } void getmap(int n) { for (int i = 0;i <= n;++i) { for (int j = 0;j <= n;++j) { Sint(d[i][j]); } } } int main() { int n; while (Sint(n) == 1&&n) { mem(d,0);mem(dp,inf); getmap(n); floyd(n); int V = (1<<(n+1))-1;//n+1个1的二进制数 for (int i = 0;i <= V;++i)//枚举状态i { for (int j = 0;j <= n;++j)//枚举当前要到的点 { dp[1<<j][j] = d[0][j]; if (i&(1<<j))//这个点在状态i中 { for (int k = 0;k <= n;++k)//枚举中间转换的点 { if (j == k) continue; if (i&(1<<k)) { dp[i][j] = min(dp[i][j],dp[i^(1<<j)][k]+d[k][j]); } } } } } int ans = inf; for (int i = 0;i <= n;++i) { ans = min(ans,dp[V][i]+d[i][0]); } Pintc(ans,'\n'); } return 0; } 很多事情哪有那么多缘由，外人看来不可理解幼稚荒唐到一定程度，在你而言，不过是喜欢而已。