POJ 3311 Hie with the Pie(TSP问题DP解)

本文主要是介绍POJ 3311 Hie with the Pie(TSP问题DP解)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：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",&

这篇关于POJ 3311 Hie with the Pie(TSP问题DP解)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---