洛谷P1433 吃奶酪

ゝ一世哀愁。 2022-05-30 03:05 177阅读 0赞

## 题目描述 ##

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

## 输入输出格式 ##

输入格式：

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

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

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

输出格式：

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

## 输入输出样例 ##

输入样例\#1： 复制

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

输出样例\#1： 复制

7.41

dfs每一个点,外加一个剪枝（当前的长度如果比之前的长度长就跳过）

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<math.h>
    using namespace std;
    
    struct node
    {
    	double x;
    	double y;
    }point[16];
    bool vis[16];
    int n;
    double ans = 0x7fffffff;//初始答案设置为无限大
    void dfs(double x,double y,int step,double tmp)
    {
    	if (tmp > ans)//当前的长度如果比之前的长度长就跳过
    		return;
    	if (step > n)
    	{
    		ans = min(ans, tmp);
    		return;
    	}
    	for (int i = 1; i <= n;i++)
    	if (!vis[i])
    	{
    		vis[i] = true;
    		dfs(point[i].x, point[i].y, step + 1, tmp + sqrt((point[i].x - x)*(point[i].x - x) + (point[i].y - y)*(point[i].y - y)));
    		vis[i] = false;
    	}
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    		cin >> point[i].x >> point[i].y;
    	dfs(0, 0, 1,0);
    	printf("%.2f", ans);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关 P1433-吃奶酪

1 include <bits/stdc++.h> 2 using namespace std; 3 define _for(i,a,b) for(

太过爱你忘了你带给我的痛/ 2023年06月01日 08:49/ 0 赞/ 4 阅读

相关洛谷P1433 吃奶酪--Java解法(货郎担问题)

洛谷P1433 吃奶酪–Java解法(货郎担问题) [题目链接][Link 1] 解决思想本题目是一个典型的货郎担问题,即从(0,0)点出发,所有点仅经过依次(

绝地灬酷狼/ 2022年10月30日 01:28/ 0 赞/ 176 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 321 阅读

相关洛谷P1433 吃奶酪

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

ゝ一世哀愁。/ 2022年05月30日 03:05/ 0 赞/ 178 阅读

相关洛谷 P1736 创意吃鱼法

题目描述回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^\_\）。她发现，把大池子视为

女爷i/ 2022年05月27日 11:17/ 0 赞/ 169 阅读

相关洛谷 P1508 Likecloud-吃、吃、吃

题目背景问世间，青春期为何物？答曰：“甲亢，甲亢，再甲亢；挨饿，挨饿，再挨饿！” 题目描述正处在某一特定时期之中的李大水牛由于消化系统比较发达，最近一直处

落日映苍穹つ/ 2022年05月27日 03:15/ 0 赞/ 182 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 316 阅读

相关洛谷P1002题解

include<iostream> using namespace std; long long a[30][30]={0},n,m,my,m

我会带着你远行/ 2022年03月19日 04:16/ 0 赞/ 349 阅读

相关【洛谷p3958】奶酪

[奶酪【题目链接】][Link 1] 题前废话不知道说啥了啊qwq（越来越沉默寡言） ![1605606-20190705112254691-609612393.png][

矫情吗；*/ 2021年11月14日 11:10/ 0 赞/ 437 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 439 阅读