社区讨论

P1433 TLE 3个点,无助啊QWQ!!!!!

P1433吃奶酪参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo1zk7dq
此快照首次捕获于
2023/10/23 05:33
2 年前
此快照最后确认于
2023/11/03 05:58
2 年前
查看原帖

求神犇帮忙

程序如下:
CPP
#include<bits/stdc++.h>
using namespace std;
int n;
bool vis[20];
double ans = 1e10;
double x[20], y[20];
void dfs (int num, int k, double sum) {
	if (sum >= ans) return;
	if (k - 1 == n) {
		ans = min(ans, sum);
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;
		vis[i] = true;
		dfs(i, k + 1, sum + sqrt((x[num] - x[i]) * (x[num] - x[i]) + (y[num] - y[i]) * (y[num] - y[i])));
		vis[i] = false;
	}
}
int main () {
//	freopen("P1433_10.in","r",stdin);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lf%lf", &x[i], &y[i]);
	}
	dfs(0, 1, 0.0);
	printf("%.2lf", ans);
	return 0;
}
下面是第 1010 个测试点,这个程序跑了三十多秒...
CPP
15
0 0
1 1
1 -1
-1 1
-1 -1
2 2
2 0
2 -2
0 -2
-2 -2
-2 0
-2 2
0 2
1 3
1 4
答案:
CPP
21.73
例外还 TLETLE12,1312,13 两个点,求助神犇!!

回复

4 条回复,欢迎继续交流。

正在加载回复...