怎么回事,用DFS90分
  • 板块P1433 吃奶酪
  • 楼主dengyanxia
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/15 15:43
  • 上次更新2024/12/15 15:44:07
查看原帖
怎么回事,用DFS90分
1041145
dengyanxia楼主2024/12/15 15:43

我怀疑是不是我错的是2022.7.132022.7.13 洛谷做的HACKHACK数据TLETLE了,三个测试点,我两行泪啊! 请看代码:

#include <bits/stdc++.h>
using namespace std;
double x[25], y[25];
int vis[25];
int mp[25];
int n;
double ans = 1e9;
void dfs(int p, double sum) {
	if(sum >= ans) return ;
	if(p > n) {
		ans = min(ans, sum);
		return ;
	}
	for (int i = 1;i <= n;i ++) {
		if(vis[i] == 1) continue;
		vis[i] = 1;
		mp[p] = i;
		double x1, y1, x2 , y2;
		x1 = x[mp[p - 1]], y1 = y[mp[p - 1]];
		x2 = x[i], y2 = y[i];
		double anss = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
		dfs(p + 1, sum + anss);
		vis[i] = 0;
	}
}
int main () {
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> x[i] >> y[i];
	dfs(1, 0);
	printf("%.2lf", ans);
	return 0;
}

有哪位大佬指点一下。。。。大佬应该会觉得这个题很无聊。。。

2024/12/15 15:43
加载中...