美团校招笔试真题&软件开发一二面经

1.6.1 小美的送花线路

【题目描述】

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

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

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

int main() {

int n;

scanf("%d", &n);

unordered_map<int, vector<pair<int, int>>> mp;

int total = 0;

while (--n) {

int sor, des, w;

scanf("%d%d%d", &sor, &des, &w);

mp[sor].push_back({des, w});

total += w;

}

queue<pair<int, int>> q;

q.push({1, 0});

int maxLength = -1, sumLength = 0;

while (!q.empty()) {

pair<int, int> p = q.front();

q.pop();

int len = mp[p.first].size();

if (!len) {

//total += p.second;

maxLength = max(maxLength, p.second);

} else {

for (int i = 0; i < len; ++i) {

pair<int, int> tmp = mp[p.first][i];

q.push({tmp.first, p.second + tmp.second});

sumLength += (p.second + tmp.second);

}

}

}

total = total * 2 - maxLength;

cout << sumLength << ' ' << total << endl;

return 0;

}

......

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

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

资料包含：

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

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

电脑端请微信扫码>>

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

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

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