回溯搜索,点10WA,求助!!!
查看原帖
回溯搜索,点10WA,求助!!!
532029
Blind_Swallow楼主2022/3/10 20:46
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
int n, ans[15];
bool vis[15];
double x[15], y[15], len = 1e9, dis;
double dist(int i, int j)
{
	return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
double calc()
{
	double sum = 0;
	for(int i = 1; i <= n; i++)
		sum += dist(ans[i - 1], ans[i]);
	return sum;
}
void dfs(int x)
{
	if(dis >= len) return;
	if(x > n)
	{
		len = min(len, dis);
		return;
	}
	for(int i = 1; i <= n; i++)
		if(!vis[i])
		{
			vis[i] = 1;
			ans[x] = i;
			dis += dist(ans[x - 1], i);
			dfs(x + 1);
			vis[i] = 0;
			dis -= dist(ans[x - 1], i);
		}
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> x[i] >> y[i];
	ans[0] = 0; x[0] = 0; y[0] = 0;
	dfs(1);
	printf("%.2lf\n", len);
	return 0;
}
2022/3/10 20:46
加载中...