链接:https://ac.nowcoder.com/acm/contest/3402/I

   盼啊,盼啊,伴随着时钟的敲响,我们即将迎来了美好的传统佳节-春节。为了给新年增添浓浓节日气息,师弟师妹们纷纷向师姐说:“师姐我想要收大红包!”,而我们人美心善声音靓的jx师姐也很大气地说:“给,给大个的,n个够吗?”,师弟师妹:“够了,谢谢师姐,师姐真好。”,但是可爱调皮的师姐将总共n个红包给藏在了实验室228里,并给了你每个红包的坐标。机智的你当然是得拿走所有红包,但是你得移动最少的距离来拿到所有红包!!奥里给!!一开始你在(0,0)处。

输入描述:

第一行包含一个整数n(0<=n<=13)
接下来n行,每行2个实数,
表示第i个红包的坐标x,y(0<=|x|,|y|<=30)
两点之间的距离公式为
sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

输出描述:

需要走的最少距离,结果保留小数点后2位。
示例1

输入

2
-1 1
2 2

输出

4.58

解题思路:因为数据范围不大所以可以用dfs暴搜
AC代码:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
typedef long long ll;
const int maxn = 1e2+10;
double x[maxn];
double y[maxn];
double ans=1000000.0;
int vis[maxn];
double dis[maxn][maxn];
int n;
void dfs(int x,int now,double min1){//x是深度,now是现在的状态因为你要从上一状态继续走//min1记录最小值 
    if(min1>ans){
        return ;
    }
    if(x==n){
        ans=min1;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            vis[i]=1;//标记数组
            dfs(x+1,i,min1+dis[i][now]);
            vis[i]=0;
        }
    }
}
int main()
{

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));//先算出打表算出任意两点的距离
        }
    }
    dfs(0,0,0.0);
    printf("%.2lf",ans);
    return 0;
}
View Code

AC代码2:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
typedef long long ll;
const int maxn = 1e2+10;
double x[maxn],y[maxn];
double lmin=1000000.0;
double dis(int i,int j){
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int vis[maxn];
int p[maxn];
int n;
void dfs(int x,double ans){
    if(ans>lmin)return;
    if(x==n){
        lmin=ans;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            p[x]=i;
            dfs(x+1,ans+dis(p[x],p[x-1]));//p[x-1]是上一个状态
            vis[i]=0;
        }
    }

}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    dfs(0,0.0);
    printf("%.2lf",lmin);
    return 0;
}
View Code


12-26 09:55