← 返回题目列表

AtCoder · yamato_contest2019_a

A. 问题1

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

题目说明

给定一张配送区域道路网络。道路对车辆有行驶方向限制,而驾驶员推台车步行时可以沿道路双向移动。道路上给出若干允许停车的位置和若干收件地点;它们可能位于道路内部,也可能与交叉口重合。

每个配送询问指定车辆的出发停车位置和一组待投递包裹。车辆可沿有向道路移动并停在允许停车的位置;驾驶员可取出不超过台车容量的包裹,步行到收件地点,完成一批投递后回到车辆。求完成全部投递所需的最短总时间。

移动规则

  • 车辆必须遵守道路方向,只能在候选停车点停车。
  • 台车步行不受道路方向限制,可到达道路上的收件点。
  • 同一路段两点之间的代价等于它们的沿路距离,通过相连交叉口不增加额外距离。
  • 一次台车行程携带的包裹数不得超过容量,每个包裹必须恰好送达一次。

输入与输出

输入依次给出交叉口、带方向的道路、道路长度、停车点、收件点和若干配送询问。每个询问包含起始停车位置和至多 10 个包裹。对每个询问输出完成全部投递所需的最短时间,数值使用原评测器规定的距离或时间单位。

求解提示

可分别建立车辆用有向图和台车用无向图,预处理关键点间最短路,再在停车位置、台车容量和待投递包裹集合上进行状态压缩动态规划。