浅谈有限制的最短路问题

· · 算法·理论

\mathbb{PART\ I.}\quad 路径本身有限制的最短路

这一部分大多是对松弛条件进行修改，使其在每一步都满足要求。

\color{#3498db}{\text{P13534 [OOI 2023] The way home}}

::::success[Solution] 贪心地考虑如何排序来做 Dijkstra。 首先考虑如何赚钱。记录到达当前点经过的最大 $w_i$，需要钱时可以直接在最大值处表演。 表演次数最少的一定最优。对于表演次数相同的，选择当前剩余钱最多的。如果都相同，选择记录的表演赚钱最大值最大的。 跑一遍 Dijkstra 即可。 :::: ### [$\color{#3498db}{\text{P3946 ことりのおやつ（小鸟的点心）}}$ ](/problem/P3946) 给定一个 $n$ 个点 $m$ 条边的无向图，每条边有边权 $w_e$（米），行走速度恒为 $1\,\mathrm{m/s}$。点 $i$ 在时刻 $t$ 的雪深为 $h_i+qt$。起点 $s$ 与终点 $t$ 不受雪深限制。求是否存在一条从 $s$ 到 $t$ 的路径，满足其总行走时间 $T\le g$，且对路径上除 $s,t$ 外任一点 $i$ 的到达时刻 $t_i$ 均有 $h_i+q t_i\le l_i$；若存在，输出最小的 $T$，否则输出 `wtnap wa kotori no oyatsu desu!`。 --- ::::success[Solution] 将 Dijkstra 的松弛操作增加一条 `(v==s||v==t||h[v]+q*(dis[u]+w)<=l[v])` 的限制即可。 :::: ### [$\color{#3498db}{\text{P3489 [POI 2009] WIE-Hexer}}$](/problem/P3489) 有 $n$ 个城镇、$m$ 条双向道路、$p$ 种怪物和 $k$ 个铁匠 $\ (\ p,k\leq \color{red}{13}$ $)$。每条道路有通行时间、可能遇到的怪物种类；每个铁匠位于特定城镇，其打造的剑能对抗特定种类的怪物（一个城镇可能有多个铁匠）。 试找到从 $n$ 到 $1$ 的最短总通行时间路径，要求路径中每当遇到某种怪物时，此前已能从经过的城镇的铁匠处获得对抗该怪物的剑，若无法找到这样的路径则输出 $-1$。 --- ::::success[Solution] 注意到 $p\leq 13$，可以考虑使用状态压缩。令 $a_i$ 表示 $i$ 号点能获得的剑的情况（二进制位为 $1$ 表示可以获得）。对于每条边 $(u,v,t,c)$，$c$ 表示这个点的怪物情况，在跑 Dijkstra 的时候判断一下即可。 ```cpp if(xx==n){ cout<<dd<<endl; return 0; } for(auto v:e[xx]){ if((tt|v.t)==tt)pq.push({v.x,dd+v.d,tt|a[v.x]}); } ``` :::: ## $\mathbb{PART\ II.}\quad 最短路过程中有特殊要求的最短路

这一部分的题目一般会有所谓的「特殊边」，且数据范围尤其是特殊边的数量通常较小，这时候可以考虑分层图/类分层图。

\color{#3498db}{\fbox{分层图}}

\color{#3498db}{\text{P7297 [USACO21JAN] Telephone G}} \color{#3498db}{\tiny{\text{ 分层图的绝妙使用！}}}

给 N 个点，第 i 个点带颜色 b_i。和一个关于颜色的邻接矩阵 S。若 S_{i,j}=1，则所有颜色 i 的点到颜色 j 的点都有一条边。规定 i 号点到 j 号点若有一条边，则边权为 |i−j|。问图中从 1 到 N 的最短路。\ (\ K\leq \color{red}{50} )

::::success[Solution] 我们先考虑 K=1 的时候。此时有两种情况：

注意到 K\leq 50，我们自然而然地想到「按照颜色区分每一层」的分层图。令 dis_{col,pos} 为想要达到第 col 层（也就是第 col 种颜色，若 col=0 则表示原数组的那一层）的第 pos 个位置的最小代价。答案即为 dis_{0,n}。

对于一个位置 (col,pos)，如果要切换到相邻的位置 (col,pos-1) 或 (col,pos+1)，代价为 1（由题意得），如果要切换颜色为 col'（前提是 S_{col',b_{pos}}=1^*），代价为 0。

void upd(ll u,ll v,ll w){
    if(dis[v])return;
    if(w)q.push_back({v,dis[v]=dis[u]+w});
    else q.push_front({v,dis[v]=dis[u]+w});
}
ll lyr=(x-1)/n,pos=(x-1)%n+1;
if(pos>1)upd(x,x-1,1);
if(pos<n)upd(x,x+1,1);
if(s[lyr][b[pos]])upd(x,pos,0);

:::info[*为什么这里不是 S_{b_{pos},col'}=1？] 因为是要让「假的」col' 传给「真的」b_{pos}。 :::

这样就可以建图了。还可以用 01BFS 优化，这样连图都不用建了。 ::::

\color{#3498db}{\text{P5122 [USACO18DEC] Fine Dining G}}

有 n 个点，m 条无向边，有一些点有点权 k_i（题目中称为“美味值”），对于所有的节点 u，判断「经过某一个有点权的点，u 到 N 的最短路」与「u 到 N 的最短路」之差是否不大于 k_v。

::::success[Solution] 在第一篇题解里面是这么说的（已经过意译，原文使用的变量名没有事先定义）：

再对于每一次的干草堆操作，将一个虚拟节点与这个点之间建一条长度为（N 到这个个点的距离减它的美味值）的边。

其实只要把这句话读明白，理解原因就能做出来了。下面来解释一下这段话：

这里的“美味值”本质上还是分层图，相当于这个节点可以把两点之间的最短路减去它的美味值。这里我们就可以把这一个点拆成两个节点，且这两个点之间只有一条边权为它的美味值的边。

但这样会有负环，而且还有可能不止一次地经过那些不同的被拆开的点，显然是无法跑 Dijkstra 的。考虑一种优化方法：假设我们已知 u 到 N 的最短路长度为 dis_u，u 点还有一个美味值为 x 的稻草。在记录原先最短路的同时，不妨记录一下减去这个“美味值”的最短路。开一个虚拟节点（0 号节点），连一条 0 到 u，边权为 dis_u-x 的有向边。这样一来也就相当于把两点之间的最短路减去了它的美味值。

for(ll i=1,pos,x;i<=k;i++){
  cin>>pos>>x;
  e[0].emplace_back(pos,ans[pos]-x);
}

:::info[一个小技巧]{open} 如果要求多个点到同一个点的最短路，可以转换为在其反图上求这个点到多个点的最短路（当然这个题是双向边所以就没有额外建反图）。 ::: ::::

\color{#3498db}{\text{P13515 [KOI 2025 \#1] 木槿花开了}}

给定由 N 个建筑 （编号 1\sim N,c_i\in\{0,1\} 表示第 i 个建筑是否有窗户，且 c_1=c_N=0）和 M 条单向道路（第 j 条道路从 x_j 到 y_j，通行耗时 t_j 秒）组成的图，小 A 以 a+b 秒为周期，在 [k(a+b),k(a+b)+a] 闭眼，(k(a+b)+a,(k+1)(a+b)) 睁眼 (k\in\mathbb{N})；小 B 从 1 号建筑出发，需满足：在小 A 睁眼时段内仅能处于无窗户的建筑内，闭眼时段无限制；进入建筑/道路的时刻若恰好为小 A 睁眼/闭眼的瞬间则不被发现。要求判断小 B 能否在不被发现的情况下到达 N 号建筑，若能则求到达的最短时间，否则输出 -1。

::::success[Solution] 注意到如果 t_j>a 则这条边一定不能走。因此在到达终点的时候，k 一定不大于 N。我们可以枚举每个 k 发生的行为。

具体地，对于每个 k 的开始，如果到某个点的最短路 dis_u 满足 dis_u\leq a 且该点没有窗户，则这个点可以通过，可以视为这个 k 的一个「开始」，否则这个点就不能作为起点跑 Dijkstra。

if(dis[i]<=a&&c[i]==0)dis[i]=0,q.emplace(i,0);
else dis[i]=LLONG_MAX-INT_MAX;

:::info[如何更新答案？]{open} 对于这个 k，在其之前已经有了 k-1 个完整的周期，因此在这个点的真正的最短路长度应该为 (k-1)(a+b)+dis_u。 ::: :::: 此外，下面题目也用到了（类）分层图的思想（这些就水多了）：

\color{#52c41a}{\text{P4568 [JLOI2011] 飞行路线}}，很典的分层图。

\color{#52c41a}{\text{P2939 [USACO09FEB] Revamping Trails G}}，双倍经验。

\color{#52c41a}{\text{P4822 [BJWC2012] 冻结}}，连接不同层之间的边可以不为 0。

\color{#3498db}{\fbox{化边为点}}

\color{#3498db}{\text{P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava}}

在图上求出一条 1\sim n 的路径，满足这条路径上「相邻边边权之差」的绝对值之和最小。

::::success[Solution] 考虑将边建成点。对于原图中一个点发出的所有边，将这些边两两连接，两个新点之间的边权即为原先两条边边权之差的绝对值。但这样有一个很显然的问题：如果图为菊花图（或类似），那么边的数量就会卡到 O(m^2) 级别，这显然是不行的。

让我们考虑下面一张图：

可以发现，如果我们想从 5 号点走到 3 号点，并不一定要按照 5\stackrel{4}\rightarrow 1\stackrel{2}\rightarrow 3 的顺序走，5\stackrel{4}\rightarrow 1\stackrel{3}\rightarrow4\stackrel{3}\rightarrow1\stackrel{2}\rightarrow 3 的顺序同样可以取得最小代价 2。因此我们只需要将边权排序，在相邻两条边之间连边即可。这样边的数量级就变为 O(m) 级别。 :::: 类似地，下面这些题目都采用了化边为点的思想：

$\color{#9d3dcf}{\text{P6822 [PA 2012 Finals] Tax}}

\color{#3498db}{\text{CF1407E Egor in the Republic of Dagestan}}

有 n 个点，m 条有向边，每条边都有一个权值 0 或 1。你需要为每个点分配一个 0 或 1 的权值，一条边可以经过有且仅当它的起始点的颜色和边的颜色一样。问能否使 1\rightarrow n 不存在连通的路径，如果不可以，求最短路径，路径长度定义为这条路径上边的数量。

::::success[Solution] 我们要尽量地让一条边起始点的颜色和边的颜色不一样。

对于每个没有染色的点，直接设置成与其不一样的颜色即可。

reverse(e[u].begin(),e[u].end());
for(auto [v,t]:e[u]){
    if(vis[v])continue;
    if(p[v]==-1||p[v]==t^1){
        p[v]=t^1;
    }else{
        q.push(v);
        dis[v]=dis[u]+1;
        vis[v]=1;
    }
}

:::info[如果你 WA on #29]{open} 题目本身很简单，但是有一个极其坑的点：

如果你在 CF 上交的结果是

wrong answer Answer must be equal to the value of shortest path's length: output is 138, should be 137

看一下你是否用的是 vector 存图。vector 的存图方式和链式前向星是相反的，因此只需要在遍历边之前加上 reverse(e[u].begin(),e[u].end()); 即可。

尽管目前仍未知道为什么链式前向星就能过。

::: ::::

\mathbb{PART\ III.}\quad 网格上的最短路建模

对于网格上的问题，大部分的边一般只会建在相邻的格子之间，如果题目中没有类似的要求，或要求输出方案等，就需要考虑使用 BFS 等方法。

\color{#3498db}{\text{P6233 [eJOI 2019] Awesome Arrowland Adventure}}

给你一个 n\times m 的网格，其中每个格子都有一个方向（上、下、左或右）或为空白。在不走到空白、不越界的前提下，你可以对任意一个有方向的点上的方向顺时针旋转 90\degree（可以在同一/不同点上旋转一次或多次，也可以不旋转）。求出从 (1,1) 开始按照格子给出的方向走到 (n,m) 至少需要旋转多少次。

::::success[Solution] 对于一个点，往其上、下、左、右四个方向建边，边权即为「这个点要指向这个方向需要旋转多少次」，然后从 (1,1) 跑最短路即可。 ::::

\color{#3498db}{\text{P3036 [USACO16DEC] Lasers and Mirrors G}}

给定一个二维平面上的 n 个点，以及起点和终点，起点可以往上下左右任意方向走，遇到给定的点可以拐弯，求最少的拐弯次数。

::::success[Solution] 对于每个点，可以拆成上下左右四个方向的点。对于单点拆成的四个点中相反方向的点，不需要拐弯，连一条边权为 0 的边，相邻方向的点，需要拐弯，连一条边权为 1 的边。

对于原图中同行同列的点，直接连权为 0 的边。

从起点跑一遍 Dijkstra 或者 01bfs 即可。 ::::

::::info[关于这一部分——网格上的最短路]{open}

其实很多网格上的问题由于一些限制，使用最短路并不能很好地处理，因此直接 BFS 反而会更优。以下是一些例子：

\color{#9d3dcf}{\text{P14402 [JOISC 2016] 危险的滑冰 / Dangerous Skating}} 由于每次在 BFS 上不停地增加和删除「冰块」是很难的事情，因此这个需要用最短路建模。

\color{#ffc116}{\text{ABC436D Teleport Maze}} 存在复杂度为 O(nm\log nm) 的最短路解法，但不如 O(nm) 的 BFS 解法。

\color{#3498db}{\text{P1930 [USACO3.3] 亚瑟王的宫殿}} 用最短路会 TLE。

\color{#3498db}{\text{P3716 [CTSC2000] 冰原探险}} 无最短路解法，只能用 BFS。

::::

\mathbb{PART\ IV.}\ 在特殊数据范围下最短路问题的特定解法

\color{#3498db}{\text{CF1051F The Shortest Statement}}

给你一个有 n 个点，m 条边的无向连通图。有 q 次询问，每次回答从 u_i 到 v_i 的最短路的长度。\ (\ m-n\leq \color{red}{20} )

::::success[Solution] 极其冗长。极其繁琐。三个板子的结合。

注意到 m-n\leq 20。

考虑两个点 u,v 之间的最短路在什么地方取得：

对于第一种情况，我们可以直接做一遍最小生成树并对其预处理，在 O(\log n) 复杂度内求得；

对于第二种情况，因为 m-n\leq 20，因此非树边最多只有 21 条，非树边上的点最多也只有 42 个。我们可以在 Kruskal 的过程中找出这些点，并将它们标记为「特殊点」，而后对于每一个特殊点做一遍 Dijkstra，每次询问的时候枚举使用的特殊点即可。

核心代码如下：

G.Kruskal();
T.depth[1]=T.dep[1]=0,T.dfs(1,0),T.init();
for(ll i=1,u,v;i<=q;i++){
    cin>>u>>v;
    ll ans=T.getdis(u,v);
    for(ll i=0;i<G.sp.size();i++){
        ans=min(ans,G.dis[i][u]+G.dis[i][v]);
    }
    cout<<ans<<endl;
}

:::: 类似地，还有以下题目：

\color{#3498db}{\text{P9377 [THUPC 2023 决赛] 百合}}

$\mathbf{Part\ 2.}$ 中提到的 [$\color{#3498db}{\text{P7297 [USACO21JAN] Telephone G}}$](/problem/P7297)，对于点的种类较少的题，一般可以考虑分层图。 --- ## $\mathbb{PART\ EXTRA.}\quad 线段树优化建图

这一部分的建图主要与区间有关，由于对于区间中的每个数一一连边肯定不行，因此需要在线段树上对应节点建边。

\color{9d3dcf}{\text{CF786B Legacy}}

给定 n 个点，q 次操作和起点 s。

询问点 s 到所有点的最小花费。

::::success[Solution] 区间问题，很容易想到线段树，所以我们用线段树来辅助建图。对于单点连边，我们直接连。对于区间问题，我们对于从区间到点和点到区间分别建一棵线段树，线段树的叶子节点为原来的点，其他节点对应区间。以点到区间为例，进行一次修改，从原来节点向树上对应区间节点建边即可，区间到点同理。 ::::

类似地，还有 \color{9d3dcf}{\text{P7669 [JOI 2018 Final] 月票购买 / Commuter Pass}}。

\color{#728dcf}{\text{最短路题单 }\mathtt{I}}\text{（黄绿为主）}

\color{#728dcf}{\text{最短路题单 }\mathtt{II}}\text{（蓝紫为主）}