专题：最短路（四）—— 建模与变形

本讲定位：图论系列第八讲，也是全系列的思维转换重点。前三讲把三个算法讲完了，但 CSP-S 的图论题九成不考”你会不会写 Dijkstra”，考的是”你能不能看出这题是最短路，以及在哪张图上跑”。本讲给出五个建模模型：分层图、改松弛式、虚拟点与拆点、二分答案 + 最短路判定、最短路计数与最短路 DAG。做了七组实测，其中三个结论值得先记住：分层图题答案写成 dis[t][k] 而不是 $\min_j dis[t][j]$，实测错 13.3%；次短路里顺手加一个 vis 数组，实测错 56.0%；而第 05 讲那个”漏写也只是常数问题”的 if (d > dis[u]) continue，在最短路计数里漏写直接错 25.3%——同一行代码，在两个问题里一个是效率问题、一个是正确性问题。文中所有代码经 g++ -O2 -std=c++14 -Wall 编译运行，P4568、P1144、P2865、P1462、P1073 五道题与洛谷官方样例核对通过。

前置知识：第 05 讲（Dijkstra、松弛操作、懒删除与那个 if (d > dis[u]) continue）、第 06 讲（SPFA、最长路对偶、“轮数即边数”）、第 04 讲（拓扑序与 DAG 上递推）。第 5 节要用到二分答案（顶层 08 讲，未写完的话本讲第 5.1 节给了自足的讲法）。第 6 节要用到第 04 讲 P4017 的”取模计数”经验。

适合对象：整讲标 S——这是 CSP-S 复赛的核心内容。CSP-J 冲一等的同学可以只看第 3.2 节（瓶颈路）和第 6.1 节（BFS 计数），这两块 J 组偶见；其余部分等复赛冲 S 时再回来。第 3.3 节末段与第 4.3 节标 S⭐。

1. 三个算法都会了，为什么还是做不出题

先看四个题面片段。它们都是最短路题，但没有一个直接问”最短路是多少”：

“你可以让至多 $k$ 条航线免费，求最小花费。”（P4568 飞行路线）
“求一条路径，使路径上最大的拥挤度最小。”（P1396 营救）
“求第二短的路径长度，路径可以重复经过点和边。”（P2865 Roadblocks）
“在一个城市买、在之后经过的某个城市卖，求最大差价。”（P1073 最优贸易）

第一题多了一个”用了几次免费”的维度；第二题把”路径长度”的定义从求和改成了取最大；第三题要的不是最优解而是次优解；第四题连”边权”都没有，只有点权。

前三讲教的是”给定一张图和一个松弛式，怎么快速跑完”。本讲教的是”图和松弛式从哪来”。

这五个模型可以概括成一句话：

模型	一句话	改的是什么
分层图	状态不只是”在哪个点”，还有”用掉了几次机会”	改点集（点变多了）
改松弛式	路径的”长度”不一定是边权之和	改松弛式（$+$ 变成 $\max$、$\times$、双数组……）
虚拟点与拆点	多源多汇、点权，都可以靠加点加边转成标准形式	改边集（边变多了）
二分 + 最短路	求最优难，判可行易	改问题（最优化变判定）
最短路计数 / DAG	最短路不止一条，它们组成一张 DAG	改统计量（不问长度问条数）

注意这四类”改”是可以叠加的：P1073 就是”拆点 + 分层图 + 最长路”三个同时用。所以本讲不是五个孤立的套路，而是四个可以自由组合的零件。

2. 分层图：状态里多一维

2.1 从”可以免费 $k$ 条边”说起

P4568 [JLOI2011] 飞行路线：$n$ 个城市（编号 $0 \sim n-1$）、$m$ 条双向航线，第 $i$ 条的价格为 $c_i$。你有 $k$ 张免票，可以让至多 $k$ 条航线的价格变成 0。求 $s$ 到 $t$ 的最小花费。$2 \le n \le 10^4$，$1 \le m \le 5\times10^4$，$0 \le k \le 10$。

为什么不能直接跑 Dijkstra：因为”在某个点上的最优状态”不再是一个数了。你走到城市 $u$ 时，手上可能还剩 3 张票，也可能一张都不剩——这两种情况以后能走出的最优结果完全不同，不能合并成一个 dis[u]。

一句话判据：当”到达同一个点”的两种情形不能互相替代时，dis 就该多一维。