50分求助(TLE)
查看原帖
50分求助(TLE)
1390387
vector_STL_楼主2025/1/23 11:39
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n,  f[N];
bool a[N];
double minn=1145145.1919820;
struct coordinate{
	double x,y;
};
double lon(coordinate a,coordinate b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
coordinate g[N];
void dfs(int k) {
	if (k == n + 1) {
		double sum=0;
		sum+=lon(g[0],g[f[1]]);
		for (int i = 1; i < n; i++) {
			sum+=lon(g[f[i]],g[f[i+1]]);
		}
		if(sum<minn){
			minn=sum;
		}
		return ;
	} else
		for (int i = 1; i <= n; i++) {
			if (a[i] != 1) {
				f[k] = i;
				a[i] = 1;
				dfs(k + 1);
				f[k] = 0;
				a[i] = 0;
			}
		}
}


signed main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>g[i].x>>g[i].y;
	}
	g[0].x=0,g[0].y=0;
	
	dfs(1);
	cout<<fixed<<setprecision(2)<<minn;
	return 0;
}
2025/1/23 11:39
加载中...