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

Question

题目描述

小明非常喜欢喝酒，这天小刚把房间里面的酒全部藏起来了。
小明想喝，但又想走最少的路程。
为了简化题目，我们把酒的总数（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

麻烦给个解释，谢谢。

Answer 1

#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;
}