lessons/课程/05-最短路与类最短路/01-建图松弛与01状态图.md

最短路模型选择：建图、松弛与 0-1 状态图

若“松弛”和“何时定案”还陌生，先完成 课前零食：从乱走到松弛。

本节目标

学完后，你应能把“达到状态的最小代价”建成图，按边权选择 BFS、0-1 BFS 或 Dijkstra，解释松弛不变量，并通过扩展状态处理免费切换等全局模式。

前置知识与课前自测

前置：队列、优先队列、无向/有向图、long long。

1. 边权只有 0 和 1 时，普通 BFS 为什么不正确？Dijkstra 是否正确但浪费？
2. Dijkstra 弹出一个旧距离条目时，为何可以直接丢弃？
3. “按开关后所有边通行性翻转”能否只把每个原点保留一次？

自测答案

1. 普通 BFS 最小化边数，不最小化权和；Dijkstra 正确，0-1 BFS 用双端队列更直接。 2. 若条目距离不等于当前 `dist[v]`，已有更短路线到达，旧条目不可能产生更优松弛。 3. 不能；同一地点在两种开关模式下可走的边不同，必须是两个状态。

问题动机与算法选择

先问“状态是什么、一次合法动作是什么、动作代价是什么”，再选择算法：

边权	算法	复杂度
全部为 1	BFS	$O(V+E)$
只有 0/1	0-1 BFS	$O(V+E)$
全部非负	堆优化 Dijkstra	$O((V+E)\log V)$
含负边	Bellman-Ford / DAG DP 等	见差分约束章节

Dijkstra 维护 dist[v] 为当前已知上界；每次取未确定点中距离最小者。因所有未走边非负，任何绕过其他未确定点的路线都不会更短，所以该距离可最终确定。负边会破坏这一论证。

核心知识：松弛不变量

松弛 dist[v] > dist[u] + w 的含义是发现一个更好的可行上界。BFS、0-1 BFS 与 Dijkstra 的差别主要在于按什么顺序取出待扩展状态；这个顺序必须保证状态被最终确定时，不会再有尚未处理的路径把它变得更小。

实现指南

• 距离上界用 numeric_limits<long long>::max()/4，避免 INF+w 溢出。
• 优先队列存 (distance, vertex)；弹出后检查 if (d != dist[v]) continue。
• 不要用 visited 阻止一个尚未弹出的点被再次松弛。
• 状态扩展后先估算 $|V'|,|E'|$，模式数乘原规模仍需过限制。

精选例题 1：Super Takahashi Bros.

来源信息与题意

• VJudge：AtCoder-abc340_d Super Takahashi Bros.
• 原题：AtCoder ABC340 D
• 大致难度：模型建立；考点：动作建有向边、Dijkstra

有 $2\le N\le2\times10^5$ 个关卡。对每个 $i<N$，花 $A_i$ 可开放 $i+1$，或花 $B_i$ 可开放 $X_i$；费用至 $10^9$。求从可玩关卡 1 到可玩关卡 $N$ 的最小总时间。

Hint 1

把“当前可玩关卡”作为点，每个动作作为一条带权有向边。

Hint 2

边权全为正，但 `X_i` 可向前或向后，不能按关卡编号 DP。

Editorial 与证明

对每个 $i<N$ 加边 $i\to i+1$ 权 $A_i$、$i\to X_i$ 权 $B_i$，从 1 运行 Dijkstra。任一游戏动作序列与图上一条路径一一对应且代价相同，所以最短路径就是最少时间。复杂度 $O(N\log N)$，距离用 long long。

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

for each stage i:
    add edge i -> i+1 with cost A[i]
    add edge i -> X[i] with cost B[i]
dist = Dijkstra(graph, source=1)
output dist[N]

完整 GNU C++17 参考实现见附件：AtCoder-abc340_d.cpp

复盘与变式

若对所有 $i$ 都有 $X_i>i$，图是 DAG，可按编号或拓扑序 DP 去掉对数；本题未给该条件，不能擅自使用。

精选例题 2：Crystal Switches

来源信息与题意

• VJudge：AtCoder-abc277_e Crystal Switches
• 原题：AtCoder ABC277 E
• 大致难度：提高；考点：两层状态图、0-1 BFS

无向图有 $N,M\le2\times10^5$。每条边标记 0/1，初始仅 1 边可走；在指定的 $K$ 个点可免费按开关，使全图 0/1 通行性翻转。求从 1 到 $N$ 的最少移动次数，不能到达输出 -1。图可有重边或不连通。

Hint 1

状态是 `(所在点, 当前可通行标签)`，不是只有所在点。

Hint 2

走一条当前可用边代价 1；在开关点切换层代价 0。

Hint 3

扩展图边权只有 0/1，用双端队列：0 边放队首，1 边放队尾。

Observations、Editorial 与证明

建立两层点 $(v,0),(v,1)$。原边标签 $a$ 只在第 $a$ 层连接两个端点，代价 1；开关点的两层状态互连，代价 0。初态 $(1,1)$，答案是终点两层距离较小者。

任何真实行动序列都对应状态图路径，反之每条状态边都是合法移动或按键；路径权只累计 Move 次数。因此 0-1 BFS 最短权即答案。扩展规模 $2N$ 点、$M+2K$ 方向边（每条原边只连到一层 a；$K$ 个开关点贡献 $2K$ 条层间边），复杂度 $O(N+M+K)$。

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

state = (vertex, currently_passable_edge_label)
for original edge with label a: connect its endpoints in layer a with cost 1
for each switch vertex: connect its two layers with cost 0
dist = zero_one_BFS(start=(1, label_1))
output min(dist[(N,0)], dist[(N,1)])

完整 GNU C++17 参考实现见附件：AtCoder-abc277_e.cpp

复盘与变式

若按开关也计一次操作，层间边权改为 1，普通 BFS 即可；若不同开关费用各异且非负，换回 Dijkstra。

精选例题 3：Jzzhu and Cities

来源信息与题意

• VJudge：CodeForces-449B Jzzhu and Cities
• 原题：Codeforces Round 257 (Div. 1)
• 难度：2000；考点：多源初始化、最短路前驱、相等距离去冗余

$n\le10^5,m\le3\times10^5$ 的连通带权无向道路图，首都为 1；另有 $k\le10^5$ 条从首都到某城市的火车，可重复到同一城。删尽量多火车，同时保持首都到所有城市的最短距离不变。

Hint 1

把每座城市最短火车长度作为初始距离，与首都距离 0 一起跑道路 Dijkstra。

Hint 2

若城市存在一条道路最短前驱 `dist[u]+w=dist[v]`，到它的火车都可删。

Hint 3

只有“最短火车达到最终距离，且没有道路最短前驱”的城市需要保留恰一条火车。

Observations、Editorial 与证明

先对同终点火车取最小值作为 Dijkstra 初值，连同首都 0 在道路图上松弛，得到使用全部火车时的最短距离。扫描道路，若某方向满足等式，标记终点有道路前驱。

正权保证沿道路最短前驱距离严格下降，最终会到首都或某个必须保留火车的城市，不会形成自给自足的零权环。因此每个没有道路前驱、且最短火车等于最终距离的城市必须且只需留一条；其余火车全删。答案为 $k-\text{needed}$。复杂度 $O((n+m+k)\log n)$。

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

train[v] = minimum train length to v
run road-only Dijkstra with seeds (capital,0) and every finite train[v]
mark v if some road u-v satisfies dist[u] + w == dist[v]
needed = count(v where train[v] == dist[v] and v has no road predecessor)
output total_trains - needed

完整 GNU C++17 参考实现见附件：CodeForces-449B.cpp

复盘与变式

若道路允许零权，最短前驱可能形成等距环，单个 road_predecessor 不足以判断一整块是否仍需火车；需先压缩零权等距关系或在最短路子图上分析来源。

扩展与联系

• 多源最短路不是新算法：把多个源以各自初始距离入队，或加一个超级源。
• “免费切模式”通常产生 0 边；“消耗一次机会切模式”产生额外维度，可形成分层图。
• Dijkstra 只保证距离；若要计数、选最小代价前驱或恢复路径，还需在相等距离时定义附加目标。

总结与自检

1. 三类非负边权分别应选什么算法？
2. 状态扩展的点必须包含哪些会影响未来合法动作的信息？
3. 0-1 BFS 为什么把 0 边放队首？
4. 火车题中为什么“有道路最短前驱”足以删火车？正权条件用在哪里？

课后训练建议

先独立完成第一题；第二题先画两层图再编码；第三题至少构造“同城多条同长火车”“火车与道路同长”“火车先到中间城再走道路”三组测试。复盘时记录你是在选择算法前还是后才明确状态。