应用

1. 虚拟源点(多源最短路)

从虚拟源点向每个起点连一条权值为0的边。
从每个起点出发到达终点的所有路线的距离的最小值 等价于从虚拟源点出发，到达终点的所有路线的距离的最小值。

AcWing 1137. 选择最佳线路
方法1：建虚拟源点
方法2：反向建图，从终点开始求最短路

2. 分层图(拆点)

类似于DP，进行状态扩展
AcWing 1131. 拯救大兵瑞恩
思路：
状态表示：d[x, y, st]表示从起点到(x, y)这个格子且当前已经拥有的钥匙是st(二进制数)的所有路线的集和
属性：最短距离
状态转移：

1. 若(x, y)有钥匙key，一定拿

d[x, y, state | key] = min(d[x, y, state | key] , d[x, y, state])

1. 向上下左右走(a, b)，1.没有门或墙， 2.有门且有匹配的钥匙

d[a, b, state] = min(d[a, b, state], d[x, y, state] + 1

转换到图上求解
d[x, y, state] -> d[x, y, key|state]权值为0
d[x, y, state] -> d[a, b, state]权值为1
转换成最短路问题

3. 最短路求方案数

“最短路树“上进行DP
AcWing 1134. 最短路计数
思路：类似于DP求方案数，权值为1可以用bfs

4. 次短路求方案数

前提：不存在环形依赖，边权相同，用bfs，边权不同用dijkstra
背景：次短路求解
AcWing 383. 观光
思路：类似于最短路求方案数，结合分层图，最短路和次短路两层，用dijkstra求解即可
注意最短路只会被已经求出最短路的节点更新，而次短路除了被已经求出次短路的节点更新外，还有可能被当前节点更新最短路时更新！