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

输入格式：
第一行一个数n (n<=15)
接下来每行2个实数，表示第i块奶酪的坐标。
两点之间的距离公式=sqrt((x1-x2) * (x1-x2)+(y1-y2) * (y1-y2))

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

原题戳这里
深搜，记录上一个点和已经吃了多少块奶酪，再立一个flag，防止一块奶酪吃很多次
再就是剪枝，不剪枝会超时，如果距离已经大于了最小值，就不必继续进行计算了，然后轻松AC

#include <iostream>

#include <cmath>

#include <cstdio>

using namespace std;

double ds,minn=9999.0,dis[20][20],d[20][2];

int n,f[20];

void dfs(int l,int tot)

{

    if(tot==n&&minn>ds)

    {

        minn=ds;

        return ;

    }

    else if(tot==n)

        return ;

    for(int i=1;i<=n;i++)

    {

        if(f[i]==0)

        {

             f[i]=1;

             ds+=dis[l][i];

             if(ds<minn)

                dfs(i,tot+1);

             f[i]=0;

             ds-=dis[l][i];

        }

    }

}

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>d[i][1]>>d[i][2];

    for(int i=0;i<=n;i++)

        for(int j=0;j<=n;j++)

            dis[i][j]=sqrt((d[j][1]-d[i][1])*(d[j][1]-d[i][1])+(d[j][2]-d[i][2])*(d[j][2]-d[i][2]));

    dfs(0,0);

    printf("%.2lf",minn);

    return 0;

}