题目描述

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

思路

处理出每一个点的距离，然后搜索，如果当前值大于最小值就不做

这题不是最小生成树！！！！！！！！！！！！！

#include <stdio.h>
#include <cmath>
using namespace std;
double x[101],y[101];
double a[101][101];
int f[101];
int n;
double t=0,ans=9999999;
int dfs(int dep,int x)
{
    if (dep==n)
    {
        if (t<ans) ans=t;
        return 0;
    }
    for (int i=1;i<=n;i++)
        if (f[i]==0)
        {
            f[i]=1;
            t+=a[x][i];
            if (t<ans)
                dfs(dep+1,i);
            f[i]=0;
            t-=a[x][i];
        }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lf%lf",&x[i],&y[i]);
    for (int i=0;i<=n;i++)
        for (int j=0;j<=n;j++)
            a[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    dfs(0,0);
    printf("%.2lf\n",ans);
}