91. 最短Hamilton路径
摘要
Title: 91. 最短Hamilton路径
Tag: 哈密顿路径、集合类状态压缩dp、dp
Memory Limit: 256 MB
Time Limit: 5000 ms
Powered by:NEFU AB-IN
91. 最短Hamilton路径
-
题意
给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。
-
思路
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26'''
Author: NEFU AB-IN
Date: 2022-03-13 19:45:52
FilePath: \ACM\Acwing\91.py
LastEditTime: 2022-03-13 20:07:57
'''
N = 20 #必须尽可能地小，不然M是以指数性增加得，稍微不慎就会溢出
M = 1 << N
INF = int(2e9)
w = [[0] * N for _ in range(N)]
dp = [[INF] * N for _ in range(M)]
n = int(input())
for i in range(n):
w[i] = list(map(int, input().split()))
dp[1][0] = 0 # 从0走到0，路径中只有0处为1
for i in range(1 << n): #所有可能得路径
for j in range(n):
if i >> j & 1: # 挑选出终点
pre = i - (1 << j) # 优化：预先处理出 除去j点的状态
for k in range(n): #枚举倒数第二个点
if (pre >> k & 1): #i除去j这个点后要包含k，才能保证k转移到j
dp[i][j] = min(dp[i][j], dp[pre][k] + w[k][j])
print(dp[(1 << n) - 1][n - 1]) #最后结果为 全是1，且终点为n-1
