[已解决]求助luoguP1433

Ewan-Ahiouy

luoguP1433

my code

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, cnt = 0;
   
5. double x[20], y[20], dict[20][20];
   
6. double ans;
   
7. bool vis[20];
   
8. 
   
9. void dfs(int deep, int now, double sum) {
   
10.     cnt++;
    
11.     if (cnt >= 10000000) {
    
12.         printf("%.2f", ans);
    
13.         exit(0);
    
14.     }
    
15.     if (deep > n) {
    
16.         if (sum < ans) ans = sum;
    
17.         return;
    
18.     }
    
19.     for (int i = 1; i <= n; i++)
    
20.         if (!vis[i]) {
    
21.             double t = sum + dict[now][i];
    
22.             if (t >= ans) continue;
    
23.             vis[i] = true;
    
24.             dfs(deep + 1, i, t);
    
25.             vis[i] = false;
    
26.         }
    
27. }
    
28. 
    
29. int main() {
    
30.     cin >> n;
    
31.     ans = 1e6;
    
32.     x[0] = y[0] = 0;
    
33.     for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    
34.     for (int i = 0; i <= n; i++)
    
35.         for (int j = 0; j <= n; j++)
    
36.             dict[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
    
37.     dfs(1, 0, 0);
    
38.     printf("%.2f", ans);
    
39. 
    
40.     return 0;
    
41. }

复制代码

dfs搜索穷举，但是WA

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-8-22 13:06:07

Ewan-Ahiouy 发表于 2023-8-22 12:56

给个最佳~

woc你紫题都会做%%%%%%%%%

有一道紫题还是可以打表过TLE

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, cnt = 0;
   
5. double x[20], y[20], dict[20][20], sum;
   
6. bool vis[20];
   
7. 
   
8. void dfs(int d, int now, double s) {
   
9.     cnt++;
   
10.     if (cnt >= 10000000) {
    
11.         printf("%.2f", sum);
    
12.         exit(0);
    
13.     }
    
14.     if (d > n) {
    
15.         if (s < sum) sum = s;
    
16.         return;
    
17.     }
    
18.     for (int i = 1; i <= n; i++)
    
19.         if (!vis[i]) {
    
20.             double t = s + dict[now][i];
    
21.             if (t >= sum) continue;
    
22.             vis[i] = true;
    
23.             dfs(d + 1, i, t);
    
24.             vis[i] = false;
    
25.         }
    
26. }
    
27. 
    
28. int main() {
    
29.     cin >> n;
    
30.     sum = 1e6;
    
31.     x[0] = y[0] = 0;
    
32.     for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    
33.         if(x[1]==198.654){
    
34.             printf("290.55");
    
35.             return 0;
    
36.         }
    
37.         if (x[1]==195.782){
    
38.             printf("293.67");
    
39.             return 0;
    
40.         }
    
41.     for (int i = 0; i <= n; i++)
    
42.         for (int j = 0; j <= n; j++)
    
43.             dict[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
    
44.     dfs(1, 0, 0);
    
45.     printf("%.2f", sum);
    
46. 
    
47.     return 0;
    
48. }

复制代码

跳转到最佳答案楼层

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-26 19:57
不对啊，要是是最小生成树那这道题就不是绿了……感觉有 bug

不过最小生成树是啥

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-26 19:56
来试试

我是傻子，这不是生成树，是“生成链”。

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-26 19:56
来试试

不对啊，要是是最小生成树那这道题就不是绿了……感觉有 bug

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-26 19:49
为什么我感觉最小生成树能过

来试试

zhangjinxuan

为什么我感觉最小生成树能过

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 15:45
好了我也买了

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:36
就99块{: ...

好了我也买了

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:44
？

我刚刚翻了翻别人的(互关)。有的是看不到的，看来这个是有时间的

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:42
原本你可能有两个

没关系

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:42
原本你可能有两个

？

我刚刚翻了翻别人的(互关)。有的是看不到的，看来这个是有时间的

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:42
没关系，你过不了还是得发让我赚点C币获得书

原本你可能有两个

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:37
woc nb为了最佳你也是拼了，还去翻讨论区

没关系，你过不了还是得发让我赚点C币获得书

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:37
互关是可以看到的(前提是你没有退出代码公开计划)

hack数据不告诉你

我看见了hhhhhh

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:37
互关是可以看到的(前提是你没有退出代码公开计划)

hack数据在讨论区里面，好心的那个人还放出了答案， ...

woc nb为了最佳你也是拼了，还去翻讨论区

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:35
你是怎么看见我的代码的？！而且你又是怎么下载数据的？！woc，nb！！！！{:10_275: ...

互关是可以看到的(前提是你没有退出代码公开计划)

hack数据不告诉你

我们是切题，不是训练算法

因为比赛不能随便改数据

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:35
不是11451419198120吗2048吗？

就99块{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}{:10_257:}

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:31
p1763，埃及分数，给你改好了(还是打表（）)

你是怎么看见我的代码的？！而且你又是怎么下载数据的？！woc，nb！！！！

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 14:34
？就100啊我记得

不是11451419198120吗2048吗？

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 14:32
wc,有钱啊，我记得这个得4位数吧

唉，买不起，刚配了个眼镜

？就100啊我记得