Hamilton路径
程序员文章站
2022-04-28 10:07:14
普通的最短Hamilton 给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。 状压DP可以水过，附上lyd书上的代码 1 #include
- 普通的最短hamilton
给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短hamilton路径。 hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
状压dp可以水过，附上lyd书上的代码
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n;
4 int f[1<<20][20];
5 int weight[20][20];
6 int hamilton(int n)
7 {
8 memset(f,0x3f,sizeof(f));
9 f[1][0]=0;
10 for(int i=1;i<(1<<n);i++)
11 for(int j=0;j<n;j++){
12 if((i>>j)&1){
13 for(int k=0;k<n;k++){
14 if((i^(1<<j))>>k&1){
15 f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]);
16 }}}}
17 return f[(1<<n)-1][n-1];
18 }
19 int main()
20 {
21 std::ios::sync_with_stdio(false);
22 cin>>n;
23 for(int i=0;i<n;i++)
24 for(int j=0;j<n;j++)
25 cin>>weight[i][j];
26 cout<<hamilton(n);
27 return 0;
28 }