外卖骑手是一个和时间赛跑的工作。由于外卖订单一般集中在一日三餐的时间,具有时间短突发量大的特点,骑手们需要在订单集中的时间段内尽可能送出更多的订单以获得更多的收入。
骑手的工作流程大致是这样的,从一个商家出发,选择一个订单,送到目的地点,在目的地点接新的订单送到下一个目的地,如此循环。一个订单只能配送一次,骑手不能重复配送相同的订单。
从出发地点到取的地点的一次配送需要消耗1单位的时间。同一个地点可能发出多笔订单,其中一些订单可能要送往同一个目的地,这些起点和终点相同的订单可以合并配送,合并配送的多笔订单和单笔订单一样都只消耗1单位的时间。
简化起见,我们不区分商家和配送目的地点,统一视作地图上的一个地点。骑手的工作时间总时间是给定的,如果剩余的工作时间为0,则配送工作结束;如果到达目的地点之后,没有再从该地点发出的订单,则配送工作结束。
外卖骑手需要在给定的起始地点 Sn 和总工作时间 t 内,依次选择若干订单进行配送。每个订单由出发站点 s、到达站点 d 和配送费 p 三元组表示,且 s=d。若同一对 (s,d) 存在多笔订单,可将它们合并,合并后耗时仍为 1 单位,但收入为这批订单费用之和。每次配送无论合并与否,均耗时 1,且每笔订单只能配送一次。配送结束条件为工作时间用尽或当前地点无可接订单。输出骑手可获得的最大总收入及对应路径,若多条路径收入相同,则取字典序最小的路径。