CH0103 最短Hamilton路径状压DP 《算法竞赛进阶指南》

题目链接 http://noi-test.zzstep.com/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0103%20%E6%9C%80%E7%9F%ADHamilton%E8%B7%AF%E5%BE%84
分析 【CH0103 最短Hamilton路径状压DP】状压DP，状态f [ i ] [ j ] f[i][j] f[i][j] 用n n n 位二进制数i i i 来表示每个点是否被经过，同时j j j 记录当前路径终点，每次枚举j j j 的前一个点，确定上一状态，转移即可，注意求最小值，先将f f f 数组置为正无穷，令f [ 1 ] [ 0 ] = 0 f[1][0] = 0 f[1][0]=0。
AC代码

#include #include #include using namespace std; const int maxn = 25; int n, d[maxn][maxn], f[1 << 20][maxn]; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) scanf("%d", &d[i][j]); memset(f, 0x3f, sizeof(f)); f[1][0] = 0; for (int i = 2; i < (1 << n); ++i) for (int j = 0; j < n; ++j) if ((i >> j) & 1) for (int k = 0; k < n; ++k) if (k != j && ((i >> k) & 1)) f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + d[k][j]); printf("%d", f[(1 << n) - 1][n - 1]); return 0; }

CH0103 最短Hamilton路径状压DP

推荐阅读

板栗微波炉去壳方法板栗微波炉怎么好剥皮

卵子是怎么取出来的？

红绣球郁金香郁金香种球红了

海星为什么不能用手拿

松茸可以和什么一起煲鸡汤

速成家庭速成mysql

桃胶泡了一夜没泡开怎样办桃胶泡了一夜没泡开怎样办能吃吗

七号床的匕首

王族秘传的食谱怎么完成王族秘传的食谱完成攻略

按大脚趾孩子居然真长高了,按摩脚大拇指能长高吗

小图片无损放大安卓软件，有什么无损放大图片的软件

富山奇蝶几月开花富山奇蝶几月出花芽

东北腌酸菜的方法东北酸菜有什么特色

电子支付购物的步骤网上购物如何付款，货到付款是怎样付款

膀肉是哪个部位前膀肉是哪的肉

燕子的回忆

什么肉适合放小茴香，炖排骨需要小茴香吗

心理问题|怪罪父母，是在逃避成长责任！

饺子馅里的面丁怎么做

忐忑不安的安是什么意思忐忑不安是什么意思

CH0103 最短Hamilton路径 状压DP

推荐阅读

CH0103 最短Hamilton路径状压DP