dfs90TLE求调
  • 板块P1433 吃奶酪
  • 楼主cgxd
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/6/24 21:16
  • 上次更新2024/6/25 09:47:19
查看原帖
dfs90TLE求调
1272259
cgxd楼主2024/6/24 21:16
#include<bits/stdc++.h>
using namespace std;
int n;
vector<complex<double>> v(1);
double dis[205][205], ans = 1e9 + 5;
bitset<205> vis(1);
void dfs(int x, int y, double sum){
	if(sum >= ans or abs(sum - ans) <= 1e-4)
		return;
	if(y == n)
		ans = min(ans, sum);
	for(int i = 1; i <= n; ++i){
		if(!vis[i]){
			vis.set(i);
			dfs(i, y + 1, sum + dis[i][x]);
			vis.reset(i);
		}
	}
}signed main(){
	cin >> n;
	for(int i = 0; i < n; ++i){
		double a, b;
		scanf("%lf%lf", &a, &b);
		complex<double> c(a, b);
		v.push_back(c);
	}for(int i = 0; i <= n; ++i){
		for(int j = i + 1; j <= n; ++j)
			dis[j][i] = dis[i][j] = abs(v[j] - v[i]);
	}dfs(0, 0, 0);
	printf("%.2lf", ans);
	return 0;
}
2024/6/24 21:16
加载中...