首页 > 分享 > C++:小美的送花路线

C++:小美的送花路线

问题描述

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

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

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

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

示例 输入 5 1 2 3 1 3 1 1 4 2 2 5 1 输出 10 10 123456789 问题分析 需要首先考虑树的存储方式 考虑到到达任一节点的路径只有一条,因此到达该节点后更新从起始点到达该节点距离 考虑到若每次都返回,则遍历整棵树走过的所有距离为所有树枝长度的2倍,因此减去最长的路径不需要返回的一次即为实际走过的最短路径 源码 考虑向量来存储树,每个节点存储到达该节点的距离和该节点的子节点向量(包含节点编号和距离)

相关知识

字符串 (C++/CX)
常见C/C++ XML解析器比较
c++学习
c++第二次实验
C++: 水仙花数
C++中重载、重写(覆盖)的区别实例分析
vld(Visual Leak Detector) 内存泄露检测工具,Visual C++ 2008
花海漫步在杭州:春天最美的徒步路线
CCF NOI1008. 水仙花数 (C++)
送同事鲜花,送花小技巧送花常识

网址: C++:小美的送花路线 https://m.huajiangbk.com/newsview526090.html

所属分类:花卉
上一篇: 花束怎么快递,外卖鲜花怎么送
下一篇: 鲜花配送平台送花都是怎么送的呢,