蒟蒻回溯40分,那个大佬帮帮我...
查看原帖
蒟蒻回溯40分,那个大佬帮帮我...
668866
Dream_and_FACT楼主2022/7/1 22:43
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
struct ak{
	int x;
	int y;
	double dis;
}a[20];//存奶酪 
int n,qwe;
bool vis[20]; 
double ans=1e9+0.1;
vector<int> e;//存相同奶酪 
double s(ak x,ak y){//距离 
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
void dfs(int now,int sum,double ans_f){
	if(sum==0){
		ans=min(ans,ans_f);
		return ;
	}
	double minn=1e9+0.1;
	for(int i=1;i<=n;i++){
		if(!vis[i])a[i].dis=s(a[now],a[i]);
		if(!vis[i]&&a[i].dis<minn){
			e.clear();
			minn=a[i].dis;
			e.push_back(i);
		}
		else if(!vis[i]&&a[i].dis==minn){//考虑距离相等 
			e.push_back(i);
		}
	}
	for(int i=0;i<e.size();i++){//开始回溯 
		vis[e[i]]=true;
		dfs(e[i],sum-1,ans_f+minn);
		vis[e[i]]=false;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	//	a[i].dis=sum(f,a[i]);
	}
	dfs(0,n,0.0);
	printf("%.2lf\n",ans);
    return 0;
}
2022/7/1 22:43
加载中...