题目描述

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

输入输出格式

输入格式：

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

接下来每行2个实数，表示第i块奶酪的坐标。

两点之间的距离公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

输出格式：

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

输入输出样例

4

1 1

1 -1

-1 1

-1 -1

7.41

#include"stdafx.h"#include<iostream>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<map>#include<algorithm>#define INF 0x3f3f3f3fusing namespace std;int N,vis[20];double ans=INF;struct cc{    double x,y;}nod[20];double dis(int a,int b){    return sqrt((nod[a].x-nod[b].x)*(nod[a].x-nod[b].x)+(nod[a].y-nod[b].y)*(nod[a].y-nod[b].y));}void search(int x,int dep,double len){    if(len>=ans) return;    if(dep==N){        ans=min(len,ans);        return;    }        for(int i=1;i<=N;i++){        if(i==x)continue;        if(!vis[i]){            vis[i]=1;            search(i,dep+1,len+dis(x,i));            vis[i]=0;        }    }    }int _tmain(){//    freopen("01.in","r",stdin);    scanf("%d",&N);    for(int i=1;i<=N;i++)cin>>nod[i].x>>nod[i].y;    search(0,0,0.0);    printf("%.2lf",ans);    return 0;}