lessons/课程/05-最短路与类最短路/02-路径依赖与时间依赖状态.md

路径依赖与时间依赖最短路

本节目标

学完后，你应能识别“到达同一点但未来合法动作不同”的情况，把必要历史或时间规则纳入状态，并控制扩展图规模；还能证明等待策略为何可以贪心地取最早可出发时刻。

前置知识与课前自测

前置：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
• 原题：Codeforces Beta Round 55 (Div. 2)
• 难度：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 整型数组。

核心伪代码与参考实现附件

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

实现细节与复盘

width*width 在本题约 $9\times10^6$，仍能放入 int；编码三元组必须先转 long long。若 $n$ 升到 $10^5$，二维数组不可行，应只给出现过的有向边状态编号。

精选例题 2：Planets

来源信息与题意

• VJudge：CodeForces-229B Planets
• 原题：Codeforces Round 142 (Div. 1)
• 难度：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$ 为禁用时刻总数。

核心伪代码与参考实现附件

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

复盘与变式

若禁止的是“边在某时间段关闭”，不同出边的最早可走时刻不同，应在每条边上计算；若路程时间依赖出发时间且不满足 FIFO，更早到达未必支配晚到，普通 Dijkstra 可能失效。

扩展与联系

• 禁止长度为 $L$ 的序列时，朴素保存最近 $L-1$ 点会指数膨胀；若禁忌模式很多，应考虑自动机压缩历史。
• 周期交通表可把“点 + 时间模周期”建成有限状态图，但周期乘点数必须可承受。
• 状态不是越多越安全：只保留影响未来的最小充分信息，才兼顾正确与复杂度。

总结与自检

1. 为什么三元禁忌状态只需最近两个点？
2. 扩展图的一一对应证明包含哪两个方向？
3. Planets 中早到为何支配晚到？
4. 什么时间依赖会破坏 FIFO，从而破坏 Dijkstra？

课后训练建议

第一题先把状态图规模算清再编码，并用输出路径重新检查所有三元组。第二题构造禁用时刻 3,4,6，分别从 2、3、5、6 到达手算出发时刻。做完记录：哪一项历史或时间信息真正改变了下一步。