90分求助
查看原帖
90分求助
1045301
Hamburger999楼主2023/11/2 23:52
#include<bits/stdc++.h>
using namespace std;

void dfs(int i,int x);
pair<double,double> a[16];
double dist[16][16],mind=0xffffff,dqd;int n,use[16];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].first>>a[i].second;
	}
	a[0]=make_pair(0,0);
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			dist[i][j]=sqrt(pow(a[i].first-a[j].first,2)+pow(a[i].second-a[j].second,2));
		}
	}
	use[0]=1;
	dfs(0,0);
	printf("%.2lf",mind);
}

void dfs(int f,int x){
	if(f==n){
		mind=dqd;
	}
	else{
		for(int i=1;i<=n;i++){
			if(use[i]==0&&dqd+dist[x][i]<mind){
				use[i]=1;
				dqd+=dist[x][i];
				dfs(f+1,i);
				use[i]=0;
				dqd-=dist[x][i];
			}
		}
	}
}
2023/11/2 23:52
加载中...