【Luogu1433】吃奶酪

problem

solution

codes

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
typedef double LD;
const int maxn = 55;
int n, vis[maxn];
LD a[maxn], b[maxn], dis[maxn][maxn], now, ans=(int)1e9;
void dfs(int c, int p){
    //cout<<now<<"\n";
    if(now>ans)return ;//最优化剪枝
    if(c==n){ ans = min(ans,now); return ;}
    vis[p] = 1;
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            now += dis[p][i];
            dfs(c+1,i);
            now -= dis[p][i];
        }
    }
    vis[p] = 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>a[i]>>b[i];
    //预处理两点距离
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            dis[i][j] = sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));
    dfs(0,0);
    //cout<<ans<<"\n";
    printf("%.2lf\n",ans);
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80616629