← 返回题目列表

AtCoder · yamato_contest2019_b

B. 问题2

中文机器翻译题面 查看原题

题目说明

你要为宅配驾驶员制定一天的配送计划。输入给出有向道路网络、车辆停车位置、包裹的收件地点与指定时间条件,以及台车容量。车辆沿有向道路行驶;驾驶员可在停车点下车,把若干包裹装上台车,沿道路双向步行完成投递,再回到车辆继续行驶。

请输出车辆和台车的完整行动序列,在时间限制内尽可能多且尽可能早地完成配送。每个包裹最多投递一次;驾驶、停车、装卸、步行和交付都计入经过时间。

可行计划

  • 车辆只能沿允许方向移动,并只能在候选停车位置开始台车行程。
  • 台车可双向步行,但每次必须从车辆所在停车点出发并回到车辆。
  • 一次装载的包裹数不得超过容量,送达后从载荷中移除。
  • 动作按输出顺序执行,后一动作不得早于前一动作结束。
  • 无法在评测期限内送达的包裹可以不送,但不得输出矛盾或重复投递。

输入与输出

输入包含道路拓扑与长度、停车点、包裹目的地、包裹时间条件、台车容量和评测时间范围。输出为按时间排序的行动记录,描述车辆驶向的停车点、每次装载的包裹以及台车访问收件点的顺序。编号均沿用输入编号。

评分

合法方案按完成投递的数量及完成时刻计分:完成更多包裹、在指定时段内更早完成可获得更高分;违反移动、容量或时间约束的行动不会形成有效投递,严重格式错误会使方案无效。目标是最大化总得分。