最短路 I

· · 个人记录

最短路基础

前置知识

BFS
Dijkstra
Bellman-Ford & SPFA：优化 卡，可以顺手加上其中某些来卡常
负环
Floyd

其他模型

边权为 0 or 1

双端 BFS。

最长路

sol 1

拓扑排序+DAG 上 DP。

sol 2

最短路。
小于号改成大于号即可。（正确性：相当于把边权取负，输出时再取负一次。正环与最短路中负环等价）

次短路

Dij 和 SPFA 都可以跑。
核心思想为 1,v 的次短路（记为 dis1，最短路记为 dis0）一定是 dis0(1,u)+w(u,v) 或 dis1(1,u)+w(u,v)。
实现比较精妙。

void dij() {
    memset(dis,0x3f,sizeof dis);
    pq.push(Node(1,dis[1][0]=0));
    while( !pq.empty() ) {
        int u = pq.top().id, d = pq.top().dis; pq.pop();
        if( d > dis[u][1] ) continue; // 比次短路长，说明它无用
        for(int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if( d+w[i] < dis[v][0] )
                dis[v][1] = dis[v][0], pq.push(Node(v,dis[v][0]=d+w[i]));
                // 更新最短路时次短路变为原来的最短路
            else if( d+w[i] < dis[v][1] && dis[v][0] < d+w[i] ) // 严格次短
                pq.push(Node(v,dis[v][1]=d+w[i]));
                // 更新次短路时也push进堆可简化代码
        }
    }
}

伪多源最短路

给定一张图、点集 P，多次询问图中一点到 P 中点最短路的最小值

把 P 中所有点当做源点跑最短路

P5304 [GXOI/GZOI2019]旅行者

大概有两种做法：枚举中间边；多源次短路

Johnson全源最短路

LG 日报

分层图最短路

模板：分层图最短路--最通俗易懂的讲解

Q：为什么要用分层图最短路
A：在一个正常的图上可以进行若干次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以转换状态了

关键在于分析层与层之间的关系，本质是把一维的点加上分层变成二维，这启示我们可以每个点增加一维来维护一些额外的东西

P1266 速度限制

增加一维为速度

P3831 [USACO08JAN]Telephone Lines S

要求最小化最大边权，也可以二分+双端BFS

P1948 [SHOI2012]回家的路

只用换乘站和起/终点建两层点，分别连横/纵向边，换乘站的两点间边权为 1，起/终点为 0

题目

P1027 [NOIP2001 提高组] Car 的旅行路线

难点在于建图（初中几何知识）

P1078 [NOIP2012 普及组] 文化之旅

虽然是错题，但两种解法都比较有意思。

Sol 1

A-star。
受文化限制时最短路肯定不短于直接跑最短路，估价函数设为反图上从终点出发的最短路。

Sol 2

Floyd。
观察转移方程 f[i][j]=min(f[i][j],f[i][k]+f[k][j])，本质是在 i,j 中“插入”k 点来缩短最短路，因此可以用bitset维护 i,j 之间最短路所经过的文化。时间复杂度 O(\frac{n^4}{\omega})。

P1119 灾后重建

Floyd的本质：用前 k 个点作中转点更新 i,j 的最短路。 每次加点时以当前点作为 k Floyd即可。注意点从 0 开始编号。
若时间不递增则离线。

P2384 最短路

显然直接乘会爆long long，但求最短路的过程中又不能mod。因此考虑利用 \log (a\times b)=\log a+\log b 转成对数加法。记录每个点的前驱来计算答案。

P1613 跑路

由于跑路器的存在，长度最短不一定时间最短，因此边权不能设为长度。由题目中的 2^k 可以想到以时间做边权，再加上 n\le 50 ，枚举即可 n,k 计算。具体来讲，若存在长度路径 2^{k-1} 的边 (i,l),(l,j)，则存在长度为 2^k 的路径 (i,j)，同时设 (i,j) 的边权为 1。枚举 k,i,j,l 转移路径，Floyd求最短路，时间复杂度 O(64n^3)

P3753 国事访问

题面看得我想问候出题人 题还是不错的

澄清几点：双向边；要在经过的边最少的前提下使需要改变路状态的数量最小；要破坏所有不走的可用边

先统计可用边的数量 cnt，将可用边边权赋成 -1，不可用赋成 1，跑出经过的边最少的前提下边权和 cost[n]，答案即为 cnt+cost[n]。（先把所有边破坏，需要走的边不用破坏；不可用边直接修）

P5651 基础最短路练习题

题目迷惑性极强。。。
审题：“保证 G 中不存在简单环使得边权异或和不为 0。”这意味着

简证：对于任意两条从 i 到 j 的不同路径，可看作若干段重复和环，显然重复部分权值相等，环的部分题目已保证异或和为 0，即路径权值相等。

因此对原图的任意一颗生成树，预处理从 1,i 的路径权值 dis[i]，答案即为 dis[i]^dis[j]（LCA(i,j) 以上的部分相同，异或后为 0）。
值得注意的是很多题解都建出了生成树，其实没有必要。直接dfs一遍，每个点第一次访问的路径就构成了生成树。

P3953 [NOIP2017 提高组] 逛公园

AuSquare
code（洛谷数据较水）

习题