[已解决]求助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. }

复制代码

跳转到最佳答案楼层

isdkz

问题出在代码的最后一行，你使用了printf函数输出结果，但是题目要求输出结果保留两位小数，你应该使用printf函数的格式控制符"%.2f"来输出结果。

修改后的代码如下：

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. }
    

复制代码

这样就可以正确输出结果了。

Ewan-Ahiouy

isdkz 发表于 2023-8-21 12:51
问题出在代码的最后一行，你使用了printf函数输出结果，但是题目要求输出结果保留两位小数，你应该使用prin ...

我不知道你改变了什么

Ewan-Ahiouy

isdkz 发表于 2023-8-21 12:51
问题出在代码的最后一行，你使用了printf函数输出结果，但是题目要求输出结果保留两位小数，你应该使用prin ...

我无语了

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. }''' == '''#include <bits/stdc++.h>
    
42. using namespace std;
    
43. 
    
44. int n, cnt = 0;
    
45. double x[20], y[20], dict[20][20];
    
46. double ans;
    
47. bool vis[20];
    
48. 
    
49. void dfs(int deep, int now, double sum) {
    
50.     cnt++;
    
51.     if (cnt >= 10000000) {
    
52.         printf("%.2f", ans);
    
53.         exit(0);
    
54.     }
    
55.     if (deep > n) {
    
56.         if (sum < ans) ans = sum;
    
57.         return;
    
58.     }
    
59.     for (int i = 1; i <= n; i++)
    
60.         if (!vis[i]) {
    
61.             double t = sum + dict[now][i];
    
62.             if (t >= ans) continue;
    
63.             vis[i] = true;
    
64.             dfs(deep + 1, i, t);
    
65.             vis[i] = false;
    
66.         }
    
67. }
    
68. 
    
69. int main() {
    
70.     cin >> n;
    
71.     ans = 1e6;
    
72.     x[0] = y[0] = 0;
    
73.     for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    
74.     for (int i = 0; i <= n; i++)
    
75.         for (int j = 0; j <= n; j++)
    
76.             dict[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
    
77.     dfs(1, 0, 0);
    
78.     printf("%.2f", ans);
    
79. 
    
80.     return 0;
    
81. }'''
    
82. True
    
83. >>>

复制代码

陶远航

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <algorithm>
   
4. #include <cstring>
   
5. #include <cstdlib>
   
6. #include <queue>
   
7. #include <cmath>
   
8. using namespace std;
   
9. const int INF = 1e9;
   
10. int n;
    
11. double x[15];
    
12. double y[15];
    
13. double dp[15][1<<15];
    
14. inline int istrue( int A , int bit )
    
15. {
    
16.     return A&(1<<bit);
    
17. }
    
18. inline int set0( int A , int bit )
    
19. {
    
20.     return A&( ~(1<<bit) );
    
21. }
    
22. inline double dist( double x1 , double y1 , double x2 , double y2 )
    
23. {
    
24.     return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
    
25. }
    
26. void dfs( int now , int S )
    
27. {
    
28.     if( dp[now][S] != -1 ) return;
    
29.     dp[now][S] = INF;
    
30.     for( int i = 0 ; i < n ; ++i )
    
31.     {
    
32.         if( i == now ) continue;
    
33.         if( !istrue( S , i ) ) continue;
    
34.         dfs( i , set0( S , now ) );
    
35.         dp[now][S] = min( dp[now][S] , dp[i][ set0( S , now ) ] + dist( x[i] , y[i] , x[now] , y[now] ) );
    
36.     }
    
37. }
    
38. int main()
    
39. {
    
40.     cin >> n;
    
41.     for( int i = 0 ; i < n ; ++i ) cin >> x[i] >> y[i];
    
42.     for( int i = 0 ; i < n ; ++i )
    
43.     {
    
44.         for( int j = 1 ; j < (1<<n) ; ++j )
    
45.         {
    
46.             dp[i][j] = -1;
    
47.         }
    
48.     }
    
49.     for( int i = 0 ; i < n ; ++i ) dp[i][1<<i] = dist(0,0,x[i],y[i]);
    
50.     for( int i = 0 ; i < n ; ++i ) dfs( i , (1<<n)-1 );
    
51.     double mn = INF;
    
52.     for( int i = 0 ; i < n ; ++i ) mn = min( mn , dp[i][(1<<n)-1] );
    
53.     printf( "%.2lf" , mn );
    
54.     return 0;
    
55. }
    

复制代码

Ewan-Ahiouy

陶远航 发表于 2023-8-21 12:58

抄题解好玩吗，无聊

sfqxx

Ewan-Ahiouy 发表于 2023-8-21 13:02
抄题解好玩吗，无聊

打击

sfqxx

啊哈哈，本来是AC的，结果被Hack数据给Hack掉了

Ewan-Ahiouy

sfqxx 发表于 2023-8-21 13:48
啊哈哈，本来是AC的，结果被Hack数据给Hack掉了

陶远航

根据你提供的代码和题目信息，这是一个求解旅行商问题（TSP）的问题。代码中使用DFS搜索进行穷举，但是在进行深度优先搜索时，没有正确处理剪枝条件。

问题出现在以下代码段中：

1. if (t >= ans) continue;
   

复制代码

这里的剪枝条件是当前路径长度已经超过了当前最优解ans时，直接进行下一次循环。然而，这个判断条件是错误的。因为题目要求的是找到全局最小的路径长度，而不仅仅是找到比当前路径短的路径。所以这个剪枝条件应该被修改为：

1. if (sum + dict[now][ i] >= ans) continue;
   

复制代码

这样才能保证在搜索过程中能够正确地对路径长度进行剪枝。

请将以上代码修改后再次尝试，希望能够解决你的问题。如果还有其他疑问，请随时提问。
如果问题已经解决，请设置最佳答案

Ewan-Ahiouy

陶远航 发表于 2023-8-21 14:15
根据你提供的代码和题目信息，这是一个求解旅行商问题（TSP）的问题。代码中使用DFS搜索进行穷举，但是在进 ...

还是WA

sfqxx

Ewan-Ahiouy 发表于 2023-8-21 15:07
还是WA

我喜欢打表

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. }

复制代码

虽然但是过了

sfqxx

@Ewan-Ahiouy

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 11:10
我喜欢打表

sfqxx

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

sfqxx 发表于 2023-8-22 13:06
给个最佳~

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

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 13:07

给个最佳~

sfqxx

你有洛谷的进阶版的算法书吗？

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 13:12
你有洛谷的进阶版的算法书吗？

有

Ewan-Ahiouy

sfqxx 发表于 2023-8-22 13:06
给个最佳~

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

你把我的那题被hack的紫题给A了呗QWQ