CF864F Cities Excursions 题解

zrl123456 · 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