90分TLE求助
  • 板块P1433 吃奶酪
  • 楼主ENTERIT
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/6 18:52
  • 上次更新2024/3/6 21:08:08
查看原帖
90分TLE求助
970670
ENTERIT楼主2024/3/6 18:52
#include<bits/stdc++.h>
using namespace std;
int n;
struct p
{
	double x;
	double y;
	bool vis;
}a[20];
double ans;
double d(int m, int n)
{
	double v = sqrt((a[m].x-a[n].x)*(a[m].x-a[n].x)+(a[m].y-a[n].y)*(a[m].y-a[n].y));
	return v; 
}
double s[1001][1001];
void dfs(int sum, int now, double ds)
{
	if(ds > ans) return ;
	if(sum == n)
	{
		ans = min(ds, ans);
		return ;
	}
	for(int i = 1; i <= n; i++)
	{
		if(a[i].vis == false)
		{
			a[i].vis = true;
			dfs(sum+1, i, ds+s[now][i]);
			a[i].vis = false;
		}
	}
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lf%lf", &a[i].x, &a[i].y);
	}
	for(int i = 0; i <= n; i++)
	{
		for(int j = 0; j <= n; j++)
		{
			s[i][j] = d(i, j);
		}
	}
	a[0].x = 0;
	a[0].y = 0;
	ans = 1e9;
	dfs(0, 0, 0);
	printf("%.2lf", ans);
	return 0;
}
2024/3/6 18:52
加载中...