大佬帮帮,dfs只过了两个点QAQ
查看原帖
大佬帮帮,dfs只过了两个点QAQ
967480
jiunichenyin楼主2024/3/16 20:34
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#define maxn 1000010
using namespace std;
double n,nmins=1e10,sum=0;
struct point{
	int x, y;
}p[maxn];
int points[500][500];
double k(point a,point b){
	double ax = a.x, ay = a.y, bx = b.x, by = b.y;
	return pow(pow(ax - bx, 2) + pow(ay - by, 2), 0.5);
}
void dfs(int x,point a) {
	if (x > n) {
		nmins = min(nmins, sum);
		return;
	}
	for (int i = 1; i <= n; ++i) {
		//cout << p[i].x << " " << p[i].y << " " << x<<" "<< points[p[i].x][p[i].y] << " []" << endl;
		if (points[p[i].x][p[i].y] != 0) {
			continue;
		}
		//cout << p[i].x << " " << p[i].y << " " <<x<<" "<<n <<" ";
		points[p[i].x][p[i].y] = 1;
		point b = p[i];
		sum+=k(a, b);
		cout << sum<<endl;
		dfs(x + 1, b);
		sum -= k(a, b);
		points[p[i].x][p[i].y] = 0;
	}
	cout << endl;
}
int main() {
	memset(points,0, sizeof(points));
	cin >> n;
	p[0].x = 0; p[0].y = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> p[i].x >> p[i].y;
	}
	dfs(1, p[0]);
	cout <<fixed<<setprecision(2)<<nmins;
	return 0;
}
2024/3/16 20:34
加载中...