AlgoMooc
← 返回题库

X5023. 小慕的极限配送挑战

困难通过率 41% · 提交 17 · 通过 7
动态规划图论贪心字符串

小慕正在开发一个城市配送调度系统,她需要为一批订单规划最优的配送路线。每个订单都需要从一个地点送到另一个地点,完成一次配送需要耗费1。如果多个订单具有相同的起点和终点,那么她可以一次性完成这些配送,只消耗1单位时间。 城市中共有 N 个不同的地点,某些地点之间存在需要配送的订单。每个订单以三元组 `[s, d, p]` 表示,表示需要将订单从地点 s 送到地点 d,成功送达后可以获得 p 元报酬(其中 `s != d`)。 现在,小慕从一个指定的起点 S_n 出发,并拥有 t 单位的总配送时间。请帮助她规划配送路径,使得在规定时间内能够赚取的收入最大,并输出这条最佳的配送路径(即小慕依次经过的地点编号序列)。 如果存在多条路径可以获得相同的最高收入,请输出其中的一条。

提示:带虚线的词点一下有通俗解释。

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。