会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
建模。 把起点/终点记作 0 号点，第 i 个订单记作 i 号点。因为每次只能上下左右走一格，"两点之间的最短移动时间"就是曼哈顿距离 d(i,j)=∣xi−xj∣+∣yi−yj∣。一个配送方案等价于一个访问顺序 0→p1→p2→⋯→pn→0，每段都走最短路；到达 pk 的时刻就是前 k 段距离之和。题目把"到达时刻早于 startTime"直接判为违规（不允许提前到达后等待），所以不能靠绕路或等待来"补"时间。每个订单只需交付一次——重复经过某订单的坐标只会让交付时刻更晚，不会让任何约束更容易满足，因此方案可以用"访问排列"完整刻画。
载重校验。 出发时一次性装上全部订单货物，因此只要 ∑weight>capacity，任何路径都不合法，直接返回 -1；否则载重在配送过程中不再成为约束。
为什么不能直接用状压 DP 求最优。 常见的 TSP 状压 DP 用「已访问集合 + 最后位置」做状态，其正确性依赖"到达越早越好"这一单调性。但本题不允许等待：到达早于 startTime 同样违规，于是"更早到达"并不总是更优，状态之间不存在支配关系，最优子结构被时间窗破坏，状压 DP 无法直接给出最优值。
可行做法：枚举访问顺序 + 分支定界（DFS 剪枝）。 本解法适用于 N 较小（如 N ≤ 10）的场景：N = 10 时全排列 10! = 3.6M，配合下面的剪枝，实际搜索量远小于这个上界。
