建模。 把起点/终点记作 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，配合下面的剪枝，实际搜索量远小于这个上界。
时间限制 3 秒，空间限制 262MB。
在智能物流配送系统中，配送员需要按照最优路径完成多个订单的配送任务。
给定多个订单信息，每个订单包含：位置坐标 (x, y)；时间窗口 [startTime, endTime]，必须在指定时间范围内完成配送；订单重量 weight。
请根据如下约束条件，规划出一条能够完成所有订单配送的最优路径：
请实现 Solution 类中的 solve 方法。
| 语言 | 签名 |
|---|---|
| C++ | int solve(vector<vector<int>>& orders, int capacity) |
| Java | int solve(int[][] orders, int capacity) |
| Python | solve(self, orders: List[List[int]], capacity: int) -> int |
| JavaScript | solve(orders, capacity) |
| C | int solve(int** orders, int ordersSize, int* ordersColSize, int capacity) |
orders：二维整数数组，每个元素为 [x, y, startTime, endTime, weight]，依次表示横坐标、纵坐标、时间窗左端点、时间窗右端点、订单重量。capacity：整数，最大载重限制。ordersSize 为订单数量，ordersColSize 为每一行的列数（均为 5）。返回一个整数：完成所有配送并返回起点所需的最短总时间；若无法满足所有约束条件（载重超限或时间窗冲突），返回 -1。
输入
[[1, 2, 0, 5, 2], [3, 1, 2, 8, 3], [2, 3, 4, 10, 1]],5
输出
-1
说明
总重量 2+3+1=6 > capacity=5，返回 -1。
输入
[[1, 1, 0, 10, 2], [2, 2, 3, 15, 2]],4
输出
8
说明
(0,0)->(1,1) 距离 2、时间 2、载重 2，落在 [0,10]；(1,1)->(2,2) 距离 2、时间 4、载重 4，落在 [3,15]；(2,2)->(0,0) 距离 4、时间 8。
输入
[[0, 0, 0, 5, 1]],10
输出
0
说明
订单在起点，不需要移动，时间 0 在窗口 [0,5] 内。
Scan the QR code below with WeChat to sign in
设置一个用户名，下一步用微信扫码完成注册
请使用微信扫描下方二维码完成注册