NC50909. 最短Hamilton路径
描述
输入描述
第一行一个整数n。
接下来n行每行n个整数,其中第i行第j个整数表示点i到j的距离(一个不超过的正整数,记为a[i,j])。
对于任意的x,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且。
输出描述
一个整数,表示最短Hamilton路径的长度。
示例1
输入:
4 0 2 1 3 2 0 2 1 1 2 0 1 3 1 1 0
输出:
4
说明:
从0到3的Hamilton路径有两条,0-1-2-3和0-2-1-3。前者的长度为2+2+1=5,后者的长度为1+2+1=4C++14(g++5.4) 解法, 执行用时: 818ms, 内存消耗: 82536K, 提交时间: 2020-05-03 20:12:14
#include <bits/stdc++.h> using namespace std; int dp[1<<20][20]; int n,G[20][20]; int main(){ scanf("%d",&n); for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&G[i][j]); memset(dp,0x3f,sizeof(dp)); dp[1][0]=0; for(int i=1;i<1<<n;i++) for(int j=0;j<n;j++)if(i>>j&1) for(int k=0;k<n;k++)if((i^1<<j)>>k&1) dp[i][j]=min(dp[i][j],dp[i^1<<j][k]+G[k][j]); printf("%d\n",dp[(1<<n)-1][n-1]); return 0; }
C++(g++ 7.5.0) 解法, 执行用时: 736ms, 内存消耗: 82504K, 提交时间: 2023-07-03 11:01:47
#include<bits/stdc++.h> using namespace std; int n,f[1<<20][20],dt[20][20]; int main(){ memset(f,0x3f,sizeof(f)); f[1][0]=0; cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>dt[i][j]; for(int i=1;i<1<<n;i++) for(int j=0;j<n;j++) if(i>>j&1) for(int k=0;k<n;k++) if((i^1<<j)>>k&1) f[i][j]=min(f[i][j],f[i^1<<j][k]+dt[k][j]); cout<<f[(1<<n)-1][n-1]; return 0; }
C++(clang++11) 解法, 执行用时: 641ms, 内存消耗: 82452K, 提交时间: 2020-12-21 19:44:26
#include<bits/stdc++.h> using namespace std; int n,f[1<<20][20],a[24][24]; int main() { cin>>n; for (int i=0;i<n;i++) for (int j=0;j<n;j++) cin>>a[i][j]; memset(f,0x3f,sizeof(f)); f[1][0]=0; for (int i=1;i<1<<n;i++) for (int j=0;j<n;j++) if (i>>j&1) for (int k=0;k<n;k++) if ((i^1<<j)>>k&1) f[i][j]=min(f[i][j],f[i^1<<j][k]+a[k][j]); cout<<f[(1<<n)-1][n-1]; }