logn_sort 2022-09-06 22:41 采纳率: 50%
浏览 177
已结题

没有思路,请各位开导一下。

题目描述

小明非常喜欢喝酒,这天小刚把房间里面的酒全部藏起来了。
小明想喝,但又想走最少的路程。
为了简化题目,我们把酒的总数(n)和坐标(x,y)给你,
请你帮小明算出来,从起点(0,0)出发,喝完所有的酒,最少需要走多少米?

输入格式

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

接下来每行2个实数,表示第i杯酒的坐标。

输出格式

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

样例 #1

样例输入 #1

4
1 1
1 -1
-1 1
-1 -1

样例输出 #1

7.41

麻烦给个解释,谢谢。

  • 写回答

7条回答 默认 最新

  • 神仙别闹 2022-09-07 15:57
    关注
    #include<bits/stdc++.h> 
    using namespace std;
    struct mp{
        double x,y;
    }a[16];                              //用a数组来记录每个点的坐标
    int n,t;
    double jul[16][16],now,ans=9999999;
    bool b[16];
    void dfs(int x)
    {
        if(now>ans)return;                //剪枝
        if(t==n){
            ans=min(now,ans);
            return;
        }
        for(int i=1;i<=n;i++)
        if(!b[i])
        {
            b[i]=true;
            now+=jul[x][i];
            t++;
            dfs(i);
            b[i]=false;                   //回溯
            now-=jul[x][i];
            t--;
        }
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
        a[0].x=0;a[0].y=0;                //好像没用的初始化
        for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
        {
            double x1=a[i].x,x2=a[j].x,y1=a[i].y,y2=a[j].y;
            jul[i][j]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
            jul[j][i]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
            //记录i和j之间的距离
        }
        dfs(0);
        printf("%.2f",ans);
        return 0;
    }
    

    或者

    #include<cstdio>
    #include<iostream>
    #include<cmath>
    using namespace std;
    int n;
    double minl=(1<<31)-1;
    bool vis[16];
    struct node{
        double x,y;
    }a[16];
    void dfs(int nowp,double nowl,int step){//(当前所在的点,当前已经走的距离,当前将处理第几个点)
        if(step==n+1&&nowl<minl){//如果step==n+1说明已经有n个点处理完了,即已经遍历完,更新最小距离
            minl=nowl;
        }
        if(nowl>minl){//最优性剪枝
            return;
        }
        for(int i=1;i<=n;i++){
            if(vis[i]==0){
                vis[i]=1;
                dfs(i,nowl+sqrt((a[nowp].x-a[i].x)*(a[nowp].x-a[i].x)+(a[nowp].y-a[i].y)*(a[nowp].y-a[i].y)),step+1);
                vis[i]=0;
            }
        }
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&a[i].y,&a[i].x);
        dfs(0,0,1);
        printf("%.2lf",minl);
        return 0;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(6条)

报告相同问题?

问题事件

  • 系统已结题 9月17日
  • 已采纳回答 9月9日
  • 创建了问题 9月6日

悬赏问题

  • ¥15 想用adb命令做一个通话软件,播放录音
  • ¥30 Pytorch深度学习服务器跑不通问题解决?
  • ¥15 部分客户订单定位有误的问题
  • ¥15 如何在maya程序中利用python编写领子和褶裥的模型的方法
  • ¥15 Linux权限管理相关操作(求解答)
  • ¥15 Bug traq 数据包 大概什么价
  • ¥15 在anaconda上pytorch和paddle paddle下载报错
  • ¥25 自动填写QQ腾讯文档收集表
  • ¥15 DbVisualizer Pro 12.0.7 sql commander光标错位 显示位置与实际不符
  • ¥15 android 打包报错