样例不过,30分无超时,求调,回复必关
查看原帖
样例不过,30分无超时,求调,回复必关
1150796
封禁用户楼主2025/7/28 14:43
#include<bits/stdc++.h>
using namespace std;
int book[100], a[100];
double minn = INT_MAX;
int n;
double ans,sum;
struct w {
	double x, y;
} f[100];
double m(double a1, double a2, double b1, double b2) {
	return sqrt((b1 - a1) * (b1 - a1) + (b2 - a2) * (b2 - a2));
}
void dfs(int step) {
	if (step == n + 1) {
		minn = min(minn, ans);
		return ;
	}
	for (int i = 1; i <= n; ++i) {
		if (book[i] == 0) {
			book[i] = 1;
			a[step] = i;
			sum = ans;
			if (step == 1) {
				ans += m(0, 0, f[a[step]].x, f[a[step]].y);
			} else {
				ans += m(f[a[step - 1]].x, f[a[step - 1]].y, f[a[step]].x, f[a[step]].y);
			}
			if (ans < minn) {
				dfs(step + 1);
			}
			ans = sum;
			book[i] = 0;
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		scanf("%lf%lf", &f[i].x, &f[i].y);
	}
	dfs(1);
	printf("%.2lf", minn);
	return 0;
}
2025/7/28 14:43
加载中...