# 路径依赖与时间依赖最短路 ## 本节目标 学完后，你应能识别“到达同一点但未来合法动作不同”的情况，把必要历史或时间规则纳入状态，并控制扩展图规模；还能证明等待策略为何可以贪心地取最早可出发时刻。 ## 前置知识与课前自测 前置：BFS、Dijkstra、上一节的状态图。 1. 禁止连续经过三元组 $(a,b,c)$ 时，仅记录当前点 $b$ 能判断下一步去 $c$ 是否合法吗？ 2. 到达点 $u$ 的最早时刻是 $t$，若 $t$ 禁止出发，主动多等几秒可能让最终答案更优吗？ 3. 扩展状态写成“整条已走路径”是否总是正确？是否可行？
自测答案 1. 不能，还需知道前一个点 $a$。 2. 在边通行时间固定、只限制出发时刻时，最早合法出发支配任何更晚出发。 3. 信息上正确，但状态数指数级；只保留决定未来转移所需的最小充分历史。
## 问题动机与步步推导 经典最短路能把到达同一点的所有路径合并，是因为未来可走边只由“当前点”决定。若合法性依赖前一步或当前时刻，合并会丢信息。 设计扩展状态的三问： 1. 哪些过去信息会改变下一步合法集合或代价？ 2. 两条路径若这些信息相同，未来是否可以完全互换？ 3. 状态数与转移数是否仍在数据范围内？ 三元禁忌只看最近两个点，所以状态 `(prev,cur)` 充分；时间限制若等待只由到达时刻决定，则仍可把 `dist[cur]` 作为标签，不必把每个时刻拆成点。 ## 核心知识与正确性 扩展图法的证明通常是一一对应：原问题每个合法动作对应扩展图一条边，扩展图每条路径也能投影成合法方案，且代价相同。完成这一步后，剩下只是按边权运行标准最短路。 时间依赖 Dijkstra 还需 FIFO 性质：更早到达同一点，不会导致能到达邻点的最早时刻反而更晚。本节等待规则允许早到后原地等到任一更晚时刻，所以早到状态支配晚到状态，单标签 Dijkstra 成立。 ## 实现指南 - 状态编码前先计算乘积是否溢出 `int`，三元组哈希主动转成 `long long`。 - 父指针必须指向完整扩展状态，最后再投影回原顶点。 - 时间表已排序时用 `lower_bound` 找到达时刻，再只扫连续禁用段；不要每秒从头查找。 - 到达终点若无需继续行动，就不能额外套用“离开终点”的等待规则。 ## 精选例题 1：Shortest Path ### 来源信息与题意 - VJudge：[CodeForces-59E Shortest Path](https://vjudge.net/problem/CodeForces-59E) - 原题：[Codeforces Beta Round 55 (Div. 2)](https://codeforces.com/problemset/problem/59/E) - 难度：2000；考点：二阶状态 BFS、路径恢复、禁忌哈希 无向无权图有 $2\le n\le3000,m\le20000$，另给至多 $10^5$ 个有序禁忌三元组 $(a,b,c)$，不可连续经过这三个点。求 1 到 $n$ 的最少边数并输出一条路径；不可达输出 -1。
Hint 1状态设为 `(上一点, 当前点)`；下一步到 `next` 时检查三元组。
Hint 2初态可用虚拟前驱 0，即 `(0,1)`，禁忌点编号均从 1 开始。
Hint 3扩展图所有边权为 1，用 BFS；父指针记录前一个状态而不是只记录前一个顶点。
Hint 4最多只会访问初态加每条无向边的两个方向，但用 $(n+1)^2$ 扁平数组可简化恢复且内存仍可控。
### Observations、Editorial 与证明 状态 `(p,u)` 表示最后两点是 $p,u$。对原边 $u-v$，若 `(p,u,v)` 不在禁忌集合，就转移到 `(u,v)`，代价 1。初态 `(0,1)`。第一次到达任一当前点为 $n$ 的状态就是最短答案。 任一合法原路径的连续三元组都通过检查，映射成扩展路径；任一扩展路径的相邻状态首尾衔接，投影后也不含禁忌。边数相同，因此 BFS 最优。扩展状态实际访问 $O(m)$，扫描转移总量至多与相邻边组合有关，最坏受 $n\le3000,m\le20000$ 约束；数组空间 $O(n^2)$，约两份 36 MB 整型数组。 ### 核心伪代码与参考实现附件 ```text BFS state is (previous_vertex, current_vertex); start = (0, 1) for neighbor next of current: skip if (previous, current, next) is forbidden visit state (current, next) and store parent state stop at first state whose current vertex is N follow parent states to restore the vertex path ``` 完整 GNU C++17 参考实现见附件：[CodeForces-59E.cpp](../../参考实现/05-最短路与类最短路/CodeForces-59E.cpp) ### 实现细节与复盘 `width*width` 在本题约 $9\times10^6$，仍能放入 `int`；编码三元组必须先转 `long long`。若 $n$ 升到 $10^5$，二维数组不可行，应只给出现过的有向边状态编号。 ## 精选例题 2：Planets ### 来源信息与题意 - VJudge：[CodeForces-229B Planets](https://vjudge.net/problem/CodeForces-229B) - 原题：[Codeforces Round 142 (Div. 1)](https://codeforces.com/problemset/problem/229/B) - 难度：1700；考点：带等待的 Dijkstra、有序禁用时刻 无向正权图有 $n,m\le10^5$，边权 $1..10^4$。每个点给出若干禁止出发时刻，总数不超过 $10^5$ 且严格递增。若恰在禁止时刻到达，必须逐秒等待，直到某时刻未被禁止才能走边。求从 1 在时刻 0 出发到 $n$ 的最早到达时间。
Hint 1到达终点后无需再出发，因此终点不需要等待。
Hint 2弹出点 $u$ 的最终最短距离 $d$ 后，在其禁用数组中二分到 $d$，再跳过连续的 `d,d+1,...`。
Hint 3用得到的最早合法出发时刻加边权松弛邻点。
### Observations、Editorial 与证明 更早到达可原地等待到任何更晚时刻，因此不会劣于晚到。Dijkstra 弹出 $u$ 的最终距离 $d$ 后，取最小 $t\ge d$ 且 $t$ 不在禁用表，所有离开 $u$ 的边都从 $t$ 出发。 任何方案在 $u$ 的出发时刻不可能早于这个 $t$；选择 $t$ 又合法，所以该局部等待是支配性的。结合非负边权，标准 Dijkstra 正确。每点只在最终弹出时扫描一次连续禁用段，总时间 $O((n+m+K)\log n)$，$K$ 为禁用时刻总数。 ### 核心伪代码与参考实现附件 ```text run Dijkstra from planet 1 when finalizing u at time t (unless u is destination): binary-search t in u's sorted blocked times advance depart across the consecutive blocked run t,t+1,... relax every edge using depart + edge_weight output destination distance or -1 ``` 完整 GNU C++17 参考实现见附件：[CodeForces-229B.cpp](../../参考实现/05-最短路与类最短路/CodeForces-229B.cpp) ### 复盘与变式 若禁止的是“边在某时间段关闭”，不同出边的最早可走时刻不同，应在每条边上计算；若路程时间依赖出发时间且不满足 FIFO，更早到达未必支配晚到，普通 Dijkstra 可能失效。 ## 扩展与联系 - 禁止长度为 $L$ 的序列时，朴素保存最近 $L-1$ 点会指数膨胀；若禁忌模式很多，应考虑自动机压缩历史。 - 周期交通表可把“点 + 时间模周期”建成有限状态图，但周期乘点数必须可承受。 - 状态不是越多越安全：只保留影响未来的最小充分信息，才兼顾正确与复杂度。 ## 总结与自检 1. 为什么三元禁忌状态只需最近两个点？ 2. 扩展图的一一对应证明包含哪两个方向？ 3. `Planets` 中早到为何支配晚到？ 4. 什么时间依赖会破坏 FIFO，从而破坏 Dijkstra？ ## 课后训练建议 第一题先把状态图规模算清再编码，并用输出路径重新检查所有三元组。第二题构造禁用时刻 `3,4,6`，分别从 2、3、5、6 到达手算出发时刻。做完记录：哪一项历史或时间信息真正改变了下一步。