华师一附中OI组

标题: P1433 吃奶酪 [打印本页]

---

作者: 倚窗倾听风吹雨    时间: 2018-8-21 14:05
标题: P1433 吃奶酪
https://www.luogu.org/problemnew/show/P1433

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

输入输出格式
输入格式：
第一行一个数n (n<=15)

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

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

输出格式：
一个数，表示要跑的最少距离，保留2位小数。

输入输出样例
输入样例#1：
4
1 1
1 -1
-1 1
-1 -1
输出样例#1：
7.41

---

作者: 倚窗倾听风吹雨    时间: 2018-8-21 14:06

1. #include<iostream>
   
2. #include<cmath>
   
3. #include<iomanip>
   
4. using namespace std;
   
5. int n;
   
6. struct node
   
7. {
   
8.     double x,y;
   
9. }a[17];
   
10. double ans=99999,dis[17][17];
    
11. bool cheese[17];
    
12. void dfs(int step,int now,double len)
    
13. {
    
14.     if(len>=ans)return;
    
15.     if(step==n)
    
16.     {
    
17.         ans=min(ans,len);
    
18.         return;
    
19.     }
    
20.     for(int i=1;i<=n;i++)
    
21.     {
    
22.         if(cheese[i])continue;
    
23.         cheese[i]=1;
    
24.         dfs(step+1,i,len+dis[now][i]);
    
25.         cheese[i]=0;
    
26.     }
    
27. }
    
28. int main()
    
29. {
    
30.     cin>>n;
    
31.     for(int i=1;i<=n;i++)
    
32.     cin>>a[i].x>>a[i].y;
    
33.     a[0].x=0;a[0].y=0;
    
34.     for(int i=0;i<=n;i++)
    
35.         for(int j=0;j<=n;j++)
    
36.             dis[i][j]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
    
37.     dfs(0,0,0.0);
    
38.     cout<<fixed<<setprecision(2)<<ans<<endl;
    
39.     return 0;
    
40. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2