列表

详情


NC50909. 最短Hamilton路径

描述

给定一张 n 个点的带权无向图,点从标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入描述

第一行一个整数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=4

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++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];	
} 

上一题