高阶扩展：把等待周期压成 0-1 状态图

本节目标

面对“绿灯内必须连续移动、红灯只能停在安全点”的时间规则，分离完整周期数与本周期已用时间，用 0-1 BFS 取代对绝对时间的搜索。

前置知识与课前自测

前置：0-1 BFS、状态图、排序。

若状态只记安全岛编号，会丢失什么？
到达安全岛时绿灯恰好结束，与尚有余量的代价差别是什么？
为什么只向排序后相邻安全岛转移仍不漏最优路线？

答案

1. 本轮绿灯还剩多少时间。 2. 前者必须经历一次红灯并把轮内进度清零；后者无需新增完整周期。 3. 同方向越过中间安全岛可拆成若干相邻段，总距离和轮内进度不变。

问题动机

以绝对时间建图会把大量只差完整周期数的状态分开；只记位置又无法判断当前绿灯是否还走得动。需要保留“相位”，把完整周期折叠进距离。

精选例题：Nastya and Unexpected Guest

来源与题意

VJudge：CodeForces-1340C
原题：Codeforces 1340C
难度：2400；考点：周期状态、0-1 BFS、终点特殊处理

道路是 $[0,n]$，$n\le10^6$；有 $m\le10^4$ 个安全岛，含 0 与 $n$。绿灯 $g$ 秒、红灯 $r$ 秒，$g,r\le1000$。绿灯时每秒走一单位且不能停，只有安全岛可变向；红灯开始时必须在安全岛。求从 0 到 $n$ 的最短时间。

Hint 1

状态设为 `(island, spent)`，其中 `spent` 是当前绿灯已经走的秒数。

Hint 2

让距离只记录已经完整经历的“绿+红”周期数。

Hint 3

移动后 `spent<g` 是 0 边；`spent==g` 必须等待红灯、重置为 0，是 1 边。

Hint 4

到终点即结束；若恰在第 $g$ 秒到达终点，不能把最后一段红灯算进去。

Observations 与 Editorial

绝对时间可很大，但规则只关心时间在周期中的相位。定义状态 $(i,s)$：人在第 $i$ 个安全岛，当前绿灯已经走 $s$ 秒，$0\le s<g$。距离 cycle[i][s] 是此前已经结束并等待过红灯的完整周期数。

从 $i$ 到相邻安全岛 $j$ 距离为 $d$：

$s+d>g$ 不合法；
$s+d<g$ 转到 $(j,s+d)$，边权 0；
$s+d=g$，若还没结束旅程，就必须等红灯并转到 $(j,0)$，边权 1。

边权只有 0/1，用 deque。每弹出状态还单独检查能否在剩余 $g-s$ 秒内直接向右到达 $n$，候选真实时间为

$$ cycle(i,s)(g+r)+s+(n-d_i). $$

这一步也正确处理“恰好到终点”：到达即停止，不加红灯。

正确性证明与复杂度

任一合法行程在每次经过安全岛时产生上述状态；同一绿灯内的连续移动对应若干 0 边，绿灯用满且未结束对应一条 1 边。因此行程映射为状态路径，完整周期数与轮内时间的公式等于真实用时。

反之每条状态边都满足绿灯余量，1 边只在安全岛等待，故状态路径可还原为合法行程。非相邻跳跃可沿同方向经过的中间安全岛拆分，不引入等待或转向，所以只连相邻岛不漏解。0-1 BFS 最小化完整周期数；对同一状态轮内时间固定，故最终枚举得到最短真实时间。

状态数 $O(mg)\le10^7$，每状态至多两条转移，时间与空间均为 $O(mg)$。

实现指南、核心伪代码与附件

sort safety islands
dist[start][0] = 0
0-1 BFS over (island i, spent s):
    try finishing directly if n-position[i] <= g-s
    for adjacent island j:
        ns = s + abs(position[j]-position[i])
        if ns < g: relax (j,ns) with cost 0
        if ns == g: relax (j,0) with cost 1
answer = minimum completed*(g+r) + spent + final_distance

完整 GNU C++17 实现

状态数组不存 spent=g，该相位立即重置。
直接把 1 边权写成 g+r、0 边写成路长并不能得到普通最短路，因为轮内进度仍约束后续合法性。
若绿灯中允许原地等待，则到达安全岛后的可选相位增加，当前唯一进度转移失效。

扩展与联系

这是“商作为距离、余数作为状态”的典型模型。若每轮规则由多个阶段组成，可把余数状态改成有限自动机；只有阶段切换代价仍为 0/1 时才能继续使用 0-1 BFS。

总结与自检

请复述：为何距离只存周期数仍足够？为何终点不能作为普通 spent==g 转移处理？只连相邻安全岛的完备性依赖哪个条件？

课后训练建议

先写状态 Dijkstra 验证模型，再替换为 0-1 BFS；用小坐标全时间 BFS 对拍。卡在状态定义 25 分钟后看 Hint 1--2。

04-高阶扩展-周期内进度状态.md 4.9 KB History Raw