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;
}
推荐阅读
- 最短且最痛心的恋爱
- 两点之间直线最短，但不一定最快
- 引入Hub再生的最短帧长及主机之间距离的最大值计算
- Codeforces - 1076D - Edge Deletion （最短路+思维）
- BZOJ|BZOJ2763[JLOI2011]飞行路线【分层图最短路】
- CodeForces - 1076D Edge Deletion 最短路标记边
- 阿里云低代码音视频工厂正式上线，为企业用户提供音视频开发最短路径
- Codeforces 1076D Edge Deletion——最短路+dfs
- Codeforces|Codeforces 1076D——最短路算法
- 求最短路径