題目描述

房間里放著n塊奶酪。一只小老鼠要把它們都吃掉，問至少要跑多少距離？老鼠一開始在(0,0)點處。

輸入輸出格式

輸入格式：

第一行一個數(shù)n (n<=15)

接下來每行2個實數(shù)，表示第i塊奶酪的坐標。

兩點之間的距離公式=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))

輸出格式：

一個數(shù)，表示要跑的最少距離，保留2位小數(shù)。

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

7.41

源代碼

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 123 #define E 1e-6 using namespace std; int n; int vis[N]; double dis[N][N]; double sum; struct Node{double x;double y; }point[N]; double calculate(int i,int j)//計算兩點距離 {return sqrt( (point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y) ); } void dfs(int past,int now,double len)//已經(jīng)走過的點，上一個走的點，已經(jīng)走過的長度 {if(len>sum)//剪枝return;if(past==n){sum=min(sum,len);return;}for(int i=1;i<=n;i++)//枚舉所有點if(!vis[i])//沒有走過{vis[i]=1;dfs(past+1,i,len+dis[now][i]);vis[i]=0;} } int main() {cin>>n;for(int i=1;i<=n;i++)cin>>point[i].x>>point[i].y;point[0].x=0;point[0].y=0;for(int i=0;i<=n;i++)//預處理兩點距離for(int j=0;j<=n;j++)dis[i][j]=calculate(i,j);sum=INF;dfs(0,0,0);printf("%.2lf\n",sum);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的吃奶酪（洛谷-P1433）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。