本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-16 16:26:49

:::::info[题目基本信息] 考察：倍增，广度优先搜索 BFS，图论（$2700$）。
题目简介：
给定一个有 $n$ 个点 $m$ 条边的有向图，$q$ 次询问，每次询问所有从 $s$ 到 $t$ 的路径中经过的顶点序列字典序最小的路径顶点序列的第 $k$ 项是什么，若不存在路径或不存在最小给出 -1。
数据范围：

• $2\le n\le 3000$
• $0\le m\le 3000$
• $1\le q\le 4\times 10^5$
• $1\le s,t\le n$
• $s\ne t$
• $1\le k\le 3000$

时间限制：2s。
空间限制：250MB。
::::: 注意到 $q$ 较大，$n$ 和 $m$ 较小，考虑预处理。
首先考虑枚举 $s$ 和 $t$ 之间的一个，我们注意到枚举 $t$ 时每个点的下一个要走的点都可以唯一确定，建反图跑一遍就可以，所以我们考虑枚举 $t$。
枚举 $t$，对于每一个点 $i$，找到最小与它相连的的 $j$ 使得 $j$ 能够到达 $t$（这个可以在最开始跑 $n$ 遍 BFS 实现，后文称 $j$ 为 $i$ 的后继），建反图跑一遍判断每个点能否走字典序最小的路径到达 $t$，这样我们就可以判掉 -1，考虑如何处理答案。
枚举 $t$ 的过程中，我们找到了每一个点的后继，我们采用倍增的方式容易预处理并计算出答案。
然后做完了。
时间复杂度为 $\Theta(nm+n^2\log V+m\log m+q\log V)$，空间复杂度为 $\Theta(n^2\log V+m)$，其中 $V$ 为 $k$ 的值域。
:::::warning[坑点] 本做法比较卡空间，倍增数组需要开 short。
:::::

code