洛谷 P1433 吃奶酪 Label：dfs && 剪枝Ex

题目描述

房间里放着n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在(0,0)点处。

输入输出格式

输入格式：

第一行一个数n (n<=15)

接下来每行2个实数，表示第i块奶酪的坐标。

两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

输出格式：

一个数，表示要跑的最少距离，保留2位小数。

输入输出样例

输入样例#1：

输出样例#1：

7.41

代码

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<cmath>
 6 #include<map>
 7 #include<algorithm>
 8 #define INF 0x3f3f3f3f
 9 using namespace std;
10 
11 map<int,double> m;
12 vector<int> G[20];
13 vector<double> c[20];
14 int N,vis[20];
15 double ans=INF;
16 
17 struct cc{
18     double x,y;
19 }nod[20];
20 
21 double dis(int a,int b){
22     return sqrt((nod[a].x-nod[b].x)*(nod[a].x-nod[b].x)+(nod[a].y-nod[b].y)*(nod[a].y-nod[b].y));
23 }
24 
25 int look_up_table(double len){
26     long long H=0;
27     for(int i=1;i<=N;i++){
28         if(vis[i]) H=H*10+i;
29     }
30     if(m.count(H)){
31         if(len>m[H]) return 0;
32         m[H]=len;
33         return 1;
34     }
35     else{
36         m[H]=len;
37         return 1;
38     }
39 }
40 
41 
42 void search(int x,int dep,double len){
43     if(len>=ans) return;
44     if(!look_up_table(len)) return;
45     if(dep==N){
46         ans=min(len,ans);
47         return;
48     }
49     vis[x]=1;
50 //    puts("$");
51     for(int i=0;i<G[x].size();i++){
52         int now=G[x][i];
53         if(!vis[now]) search(now,dep+1,len+c[x][i]);
54     }
55     
56     vis[x]=0;
57 }
58 
59 int main(){
60 //    freopen("01.in","r",stdin);
61     scanf("%d",&N);
62     for(int i=1;i<=N;i++){
63         cin>>nod[i].x>>nod[i].y;
64         //scanf("%lf",&nod[i].x,&nod[i].y);
65     }
66     nod[0].x=nod[0].y=0.0;
67     for(int i=0;i<=N;i++){
68         for(int j=i+1;j<=N;j++){
69             G[i].push_back(j);
70             c[i].push_back(dis(i,j));
71             
72             G[j].push_back(i);
73             c[j].push_back(dis(i,j));
74         }
75     }
76     search(0,0,0.0);
77     printf("%.2lf",ans);
78     return 0;
79 }

90分的map>_<

//以上为map，意料之外啊

hash貌似不可以，因为自己的数据都过不了，就没有提交

至于评测的时候我觉得直接STL就好，hash试一试吧

看了下题解，我竟无言以对

回溯以及剪枝。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<cmath>
 6 #include<map>
 7 #include<algorithm>
 8 #define INF 0x3f3f3f3f
 9 using namespace std;
10 
11 int N,vis[20];
12 double ans=INF;
13 
14 struct cc{
15     double x,y;
16 }nod[20];
17 
18 double dis(int a,int b){
19     return sqrt((nod[a].x-nod[b].x)*(nod[a].x-nod[b].x)+(nod[a].y-nod[b].y)*(nod[a].y-nod[b].y));
20 }
21 
22 void search(int x,int dep,double len){
23     if(len>=ans) return;
24     if(dep==N){
25         ans=min(len,ans);
26         return;
27     }
28     
29     for(int i=1;i<=N;i++){
30         if(i==x)continue;
31         if(!vis[i]){
32             vis[i]=1;
33             search(i,dep+1,len+dis(x,i));
34             vis[i]=0;
35         }
36     }
37     
38 }
39 
40 int main(){
41 //    freopen("01.in","r",stdin);
42     scanf("%d",&N);
43     for(int i=1;i<=N;i++)cin>>nod[i].x>>nod[i].y;
44     search(0,0,0.0);
45     printf("%.2lf",ans);
46     return 0;
47 }

完了？

行吧，电脑渣13个点的数据用暴力都跑不出来怪谁咯