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

> 若“松弛”和“何时定案”还陌生，先完成 [课前零食：从乱走到松弛](00-课前零食-从乱走到松弛.md)。

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>自测答案</summary>

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

</details>

## 问题动机与算法选择

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

| 边权 | 算法 | 复杂度 |
|---|---|---|
| 全部为 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.](https://vjudge.net/problem/AtCoder-abc340_d)
- 原题：[AtCoder ABC340 D](https://atcoder.jp/contests/abc340/tasks/abc340_d)
- 大致难度：模型建立；考点：动作建有向边、Dijkstra

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

<details><summary>Hint 1</summary>把“当前可玩关卡”作为点，每个动作作为一条带权有向边。</details>
<details><summary>Hint 2</summary>边权全为正，但 `X_i` 可向前或向后，不能按关卡编号 DP。</details>

### Editorial 与证明

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

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

```text
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](../../参考实现/05-最短路与类最短路/AtCoder-abc340_d.cpp)

### 复盘与变式

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

## 精选例题 2：Crystal Switches

### 来源信息与题意

- VJudge：[AtCoder-abc277_e Crystal Switches](https://vjudge.net/problem/AtCoder-abc277_e)
- 原题：[AtCoder ABC277 E](https://atcoder.jp/contests/abc277/tasks/abc277_e)
- 大致难度：提高；考点：两层状态图、0-1 BFS

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

<details><summary>Hint 1</summary>状态是 `(所在点, 当前可通行标签)`，不是只有所在点。</details>
<details><summary>Hint 2</summary>走一条当前可用边代价 1；在开关点切换层代价 0。</details>
<details><summary>Hint 3</summary>扩展图边权只有 0/1，用双端队列：0 边放队首，1 边放队尾。</details>

### 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)$。

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

```text
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](../../参考实现/05-最短路与类最短路/AtCoder-abc277_e.cpp)

### 复盘与变式

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

## 精选例题 3：Jzzhu and Cities

### 来源信息与题意

- VJudge：[CodeForces-449B Jzzhu and Cities](https://vjudge.net/problem/CodeForces-449B)
- 原题：[Codeforces Round 257 (Div. 1)](https://codeforces.com/problemset/problem/449/B)
- 难度：2000；考点：多源初始化、最短路前驱、相等距离去冗余

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

<details><summary>Hint 1</summary>把每座城市最短火车长度作为初始距离，与首都距离 0 一起跑道路 Dijkstra。</details>
<details><summary>Hint 2</summary>若城市存在一条道路最短前驱 `dist[u]+w=dist[v]`，到它的火车都可删。</details>
<details><summary>Hint 3</summary>只有“最短火车达到最终距离，且没有道路最短前驱”的城市需要保留恰一条火车。</details>

### Observations、Editorial 与证明

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

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

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

```text
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](../../参考实现/05-最短路与类最短路/CodeForces-449B.cpp)

### 复盘与变式

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

## 扩展与联系

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

## 总结与自检

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

## 课后训练建议

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