美团开发笔试真题+代码

小美的送花线路

【题目描述】

小美是美团的一名鲜花快递员,鲜花是一种保质期非常短的商品,所以需要尽快送到客户手中,公司对于骑手的一个要求就是要规划送花的线路,使得骑手送完所有订单走的路程尽可能少。(骑手开始派送时带走了所有需要派送的花,不必每单后返回花店,路程结算是从花店出发,到送完最后一名客户为止,不计算从最后一名客户家回到花店的时间)

公司对于骑手的绩效评价是取决于两个指标,一是从花店到所有客户地址的距离之和,另一个是骑手实际走的路程。

设花店始终位于1号位置,客户共有n-1个,其编号为2~n。令dis(i,j)表示i号位置到j号位置的距离,即分别计算,和骑手实际所走的最短路程。

为了简化问题,我们约束这n个位置构成的是一棵树,即只有n-1条边在其中互相连接,且保证n个点彼此连通。

输入描述:

输出第一行包含一个正整数n,即花店和客户的总数。(1≤n≤30000)

接下来有n-1行,每行有三个整数u,v,w,表示在u和v之间存在一条距离为w的道路。(1≤w≤1000)

输出描述:

输出包含两个整数,中间用空格隔开,分别表示花店到所有客户地址的距离之和和骑手实际走的路程。

输入样例:

5

1 2 3

1 3 1

1 4 2

2 5 1

输出样例:

10 10

【解题思路】

BFS,利用map存储该节点的所有子节点的编号以及该节点到下一节点的权值,在queue中push入队时,不断更新根节点到下一节点的总代价,也就是distant(1, i),当该节点没有子节点时说明到了叶子节点处,更新最长的路径长度,最后用所有的weight的和减去该最长路径(只走一次)就是骑手走的总距离。

【参考代码】

#include <bits/stdc++.h>

using namespace std;

.........

资料全部内容请看《2025届求职宝典-理工科版

不收费,3人组团即可免费领取!已经发出10000份,涵盖各大公司求职资料,助你事半功倍!

资料包含:

  • 30+大厂面试真题+解析
  • 软件方向:阿里、腾讯、百度、小米、华为、美团......
  • 硬件方向:华为、比亚迪、汇川、新华三、中兴、海康威视......
  • 机械方向:比亚迪、华为、美的、长江存储、宁德时代......
  • 30+大厂岗位薪资爆料
  • 30+大厂offer攻略

拿offer,别犹豫,点击马上领取>>https://www.nowcoder.com/link/campus_ziliao2024-060414

电脑端请微信扫码>>

多说无益,直接上资料截图

每个方向专栏售价69元,但是参与3人组团就可免费领取

点击马上领取>>https://www.nowcoder.com/link/campus_ziliao2024-060414

全部评论

相关推荐

不愿透露姓名的神秘牛友
06-21 11:33
昨天是学校最后一场招聘会,鼠鼠去参加了,全场只有一个招聘java的岗位,上来先做一份笔试题,做完后他拿张纸对答案,然后开始问简历上的问题,深圳小厂,6-8k(题目如下),后面还有两轮面试。然后我就在招聘现场逛呀逛,看到有公司招聘电商运营,给的比上年的小厂还多,鼠鼠就去了解了下,然后hr跟鼠鼠要了份简历,虽然我的简历上面全是求职Java开发相关的内容,但是hr还是鼓励我说没关系,她帮我把简历给老板看看,下周一会给我通知。招聘会结束后鼠鼠想了一段时间,也和朋友聊了聊,发现我可能是不太适合这个方向,然后就跟爸爸说回家了给我发条微信,我有些话想跟他说说。晚上爸爸到家了,跟我发了条微信,我立马跑出图书馆跟他打起了电话,这个通话长达一个小时,主要是跟爸爸坦白说我不想找这行了,是你的儿子太没用了,想试试其他行业。然后爸爸也跟我说了很多,说他从来没有希望我毕业后就赚大钱的想法,找不到就回家去,回家了再慢慢找,实在找不到就跟他干(帮别人装修房子,个体户),他也知道工作不好找,让我不要那么焦虑,然后就是聊一些家常琐事。对于后面的求职者呢我有点建议想提一下,就是如果招实习的时间或者秋招开始,而你的简历又很差的情况下,不要说等做好项目填充完简历之后再投,那样就太晚了,建议先把熟悉的项目写上简历,然后边投边面边完善,求职是一个人进步的过程,本来就比别人慢,等到一切都准备好后再投岂不是黄花菜都凉了。时间够的话还是建议敲一遍代码,因为那样能让你加深一下对项目的理解,上面那些说法只是针对时间不够的情况。当然,这些建议可能没啥用,因为我只是一个loser,这些全是建立在我理想的情况下,有没有用还需其他人现身说法。上篇帖子没想到学校被人认了出来,为了不丢脸只能匿名处理了。
KPLACE:找研发类或技术类,主要还是要1.多投 2.多做准备,很多方面都要做准备 3.要有心理准备,投累了就休息一两天,再继续,要相信自己能找到
投递58到家等公司7个岗位
点赞 评论 收藏
分享
评论
1
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务