本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-07 08:05:47

• 题目大意： 从0点出发，不重复走过n个点的最小路径。

• 小数据，暴力或状态压缩

• 方法一： 暴力dfs+最优化剪枝

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
double dis[16][16],ans=1000000000.0,now,x[16],y[16];\/\/两点距离，答案，现在的距离，每个点的坐标
bool vis[16];\/\/奶酪是否被吃
void dfs(int pos,int num,double now) {
	if(now>ans)\/\/如果现在的距离比答案大就返回
		return;
	if(num==n) {
		if(ans>now)\/\/更新答案
			ans=now;
		return;
	}
	vis[pos]=true;
	for(int i=1; i<=n; i++) {
		if(vis[i]==false) { \/\/枚举每个没有被吃的奶酪
			dfs(i,num+1,now+dis[pos][i]);
		}
	}
	vis[pos]=false;\/\/回溯
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%lf%lf",&x[i],&y[i]);
	x[0]=0;
	y[0]=0;
	for(int i=0; i<=n; i++) \/\/预处理两点距离
		for(int j=0; j<=n; j++)
			dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
	dfs(0,0,0);
	printf("%0.2f",ans);
}

方法二：状压dp，填表法

#include<bits\/stdc++.h>
using namespace std;

struct F{
	double x, y;
} a[20];

double dist(F a, F b)
{
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double f[20][66000];
double dis[20][20];

int n;

int main()
{
	a[0].x = 0;
	a[0].y = 0;
	memset(f, 127, sizeof(f));
	\/\/ cout<<f[0][0]<<endl;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i].x >> a[i].y;	
	}	
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			dis[i][j] = dist(a[i], a[j]);
		}
	}
	dis[0][0]=0; 
	for(int i=1;i<=n;i++)
	{
		f[i][(1<<(i-1))] = dis[0][i];
	}
	int End=(1<<n)-1; 
	for(int i=1;i<=End;i++)
	{
		for(int j=1;j<=n;j++)
		{
			
			for(int k=1;k<=n;k++)\/\/ 到了k点了 
			{
				if(j == k){continue;}\/\/j 从k点到j点 
				if((i&(1<<(j-1)))&&(i & (1<<(k-1)))){
					f[j][i] = min(f[j][i], f[k][i-(1<<(j-1))]+dis[k][j]);
				} 
				
				
			}
		} 
	}
	double ans = 1e20;
	for(int i=1;i<=n;i++)
	{
		ans = min(ans, f[i][((1<<n)-1)]);
	}
	printf("%.2lf",ans);
	return 0;	
} 

• 方法三，状态压缩，刷表

#include<bits\/stdc++.h>
using namespace std;

struct F{
	double x, y;
} a[20];

double dist(F a, F b)
{
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double f[20][66000];
double dis[20][20];

int n;

int main()
{
	a[0].x = 0;
	a[0].y = 0;
	memset(f, 127, sizeof(f));
	\/\/ cout<<f[0][0]<<endl;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i].x >> a[i].y;	
	}	
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			dis[i][j] = dist(a[i], a[j]);
		\/\/	dis[j][i] = dis[i][j];
		\/\/	cout<<dis[i][j]<<" "; 
		}
	\/\/	cout<<endl;
	}
	dis[0][0]=0; 
	f[0][1]=0;
	int End=(1<<(n+1))-1; 
	for(int i=1;i<=End;i++)
	{
		for(int j=0;j<=n;j++)\/\/到了j点了 
		{
			
			for(int k=1;k<=n;k++)\/\/ 
			{
				if(j == k){continue;}\/\/j 从j点到k点 
				if((i&(1<<(j)))&&(i&(1<<(k)))==0){
					f[k][i|(1<<(k))] = min(f[k][i|(1<<(k))], f[j][i]+dis[j][k]);
					int tmp=i|(1<<(k));
				} 
				
				
			}
		} 
	}
	double ans = 1e20;
	for(int i=1;i<=n;i++)
	{
		ans = min(ans, f[i][((1<<(n+1))-1)]);
	}
	printf("%.2lf",ans);
	return 0;	
} 

• 方法四：状态压缩，记忆化写法。

#include <bits\/stdc++.h>

using namespace std;

using namespace std;
const int INF = 1e9;
int n;
double x[15];
double y[15];
double dp[15][1<<15];

inline double dist( double x1 , double y1 , double x2 , double y2 ) {
	return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
}
double dfs( int now , int S ) {\/\/s状态下，在哪个点上 
	if( dp[now][S] != -1 ) return dp[now][S];
	dp[now][S] = INF;
	for( int i = 0 ; i < n ; ++i ) {
		if( i == now ) continue;
		if( (S&(1<<i))==0 ) continue;\/\/从i点走到now点。 
		dfs( i , S-(1<<now) );\/\/这个点由哪个点转移而来 
		dp[now][S] = min( dp[now][S] , dp[i][S-(1<<now)] + dist( x[i] , y[i] , x[now] , y[now] ) );
	}
	return dp[now][S];
}
int main() {
	cin >> n;
	for( int i = 0 ; i < n ; ++i ) cin >> x[i] >> y[i];
	for( int i = 0 ; i < n ; ++i ) {
		for( int j = 1 ; j < (1<<n) ; ++j ) {
			dp[i][j] = -1;
		}
	}
	for( int i = 0 ; i < n ; ++i ) dp[i][1<<i] = dist(0,0,x[i],y[i]);
		double mn = INF;
	for( int i = 0 ; i < n ; ++i ) mn=min(mn,dfs( i , (1<<n)-1 ));

	printf( "%.2lf" , mn );
	return 0;
}