美团开发笔试真题+代码

小美的送花线路

【题目描述】

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

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

设花店始终位于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

全部评论

相关推荐

1 3 评论
分享
牛客网
牛客企业服务