玄关40pts求调
查看原帖
玄关40pts求调
1210460
封禁用户楼主2025/1/25 18:45
#include<bits/stdc++.h>

using namespace std;

const int maxn=20;
const double oo=1e20;
double x[maxn],y[maxn];
int n;

double dis(int i,int j)
{
	return sqrt((x[i]-x[j]) * (x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]));
}

double f[1<<maxn][maxn];//f[s][i] s代表哪些点走过 i代表当前在i点的时候的最短距离 

int main()
{//O(2^n*n^2)
	cin >> n;
	for (int i=0;i<n;i++)
		cin >> x[i] >> y[i];
	for (int i=0;i<(1<<n);i++)
		for (int j=0;j<n;j++)
			f[i][j] = oo;
	f[1][0]=0.0;
	for (int s=0;s<(1<<n);s++)
		for (int i=0;i<n;i++)//要从f[s][i]向外转移 
			if (s>>i&1)//要保证i是被走过的 
				for (int j=0;j<n;j++)//走到点j
					if ((s>>j&1)==0)//要保证j是没被走过的 
						f[s|(1<<j)][j] = min(f[s|(1<<j)][j], f[s][i] + dis(i,j));
	double ans=oo;
	for (int i=0;i<n;i++)
		ans = min(ans, f[(1<<n)-1][i]);
	printf("%.2f",ans);
	
	return 0;
}

请各位大佬帮我看看有什么问题?

2025/1/25 18:45
加载中...