会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
DFS暴力解法
这道题的正解是状态压缩动态规划，但是我们用朴素解法深度优先搜索也能在考试时拿到一定的分数。
要从仓站 0 出发，把客户 1…m−1 各走恰好一次，再回到仓站。到达站点 p 的时刻必须落在 [lop,hip] 里：早到就等到 lop，等候算进总时长；迟到则这条路作废。目标是回到仓站的时刻尽量小，没有合法走法就输出 −1。
- 用深度优先搜索枚举还没走过的客户。当前停在 u、时刻为 now，对每个未访问的客户 v 算出到达时刻 t=now+dur[u][v]，必要时等到 lov，超过 hiv 就剪掉。
- 所有客户都走过之后，再加上 dur[u][0] 回到仓站，同样卡 [lo0,hi0]，用合法时刻更新答案。
- 客户有 m−1 个，搜索量大约是 (m−1)!。样例和较小的 m 可以算对；m 接近 15 时会超时，所以后面再用状压。
