CF864F Cities Excursions

在 Berland 国有 $n$ 个城市，其中有 $m$ 条有向道路连接着部分城市。人们只能通过这些道路从一个城市移动到另一个城市。不存在连接同一个城市的道路。对于每一对城市 $(x, y)$，至多只有一条从 $x$ 到 $y$ 的道路。 从城市 $s$ 到城市 $t$ 的一条路径是由一系列城市 $p_1, p_2, \ldots, p_k$ 组成的序列，其中 $p_1 = s$，$p_k = t$，且对于每一个 $1 \leq i \leq k-1$，都存在一条从城市 $p_i$ 到城市 $p_{i+1}$ 的道路。该路径可以多次经过同一座城市，除了终点 $t$ 只能经过一次。 一条从 $s$ 到 $t$ 的路径 $p$ 被称为理想路径，当且仅当它在字典序上是所有起点为 $s$，终点为 $t$ 的路径中最小的。换句话说，如果 $p$ 是从 $s$ 到 $t$ 的理想路径，则对于任意另一条从 $s$ 到 $t$ 的路径 $q$，在第一个满足 $p_i \neq q_i$ 的位置 $i$ 上，有 $p_i < q_i$。 该国有一家旅行社，计划组织 $q$ 次独特的旅行：第 $j$ 次旅行从城市 $s_j$ 出发，终点为城市 $t_j$。 请你帮助旅行社，对于每一组 $(s_j, t_j)$，研究从 $s_j$ 到 $t_j$ 的理想路径。注意，有可能不存在从 $s_j$ 到 $t_j$ 的理想路径。这有两种可能的原因： - 从 $s_j$ 到 $t_j$ 根本不存在路径； - 存在从 $s_j$ 到 $t_j$ 的路径，但对于每一条这样的路径 $p$，总存在另一条路径 $q$，使得在第一个 $p_i \neq q_i$ 的位置 $i$ 上，有 $p_i > q_i$。 对于每个三元组 $s_j, t_j, k_j$（$1 \leq j \leq q$），请判断是否存在一条从 $s_j$ 到 $t_j$ 的理想路径，并输出该路径的第 $k_j$ 个城市（从 $s_j$ 到 $t_j$ 方向上的第 $k_j$ 个城市）。 对于每组 $s_j, t_j, k_j$，如果存在理想路径，从该路径中输出第 $k_j$ 个城市；如果不存在这样的路径，或者 $k_j$ 大于该路径长度，请输出 '-1'（不带引号）。

第一行包含三个整数 $n, m, q$（$2 \leq n \leq 3000$，$0 \leq m \leq 3000$，$1 \leq q \leq 4 \cdot 10^5$）——城市数量，道路数量和旅行为数。 接下来的 $m$ 行中，每行包含两个整数 $x_i, y_i$（$1 \leq x_i, y_i \leq n$，$x_i \ne y_i$），表示第 $i$ 条道路从城市 $x_i$ 指向城市 $y_i$。所有道路都是单向的。任意一对城市之间同一方向至多存在一条道路。 接下来的 $q$ 行中，每行包含三个整数 $s_j, t_j, k_j$（$1 \leq s_j, t_j \leq n$，$s_j \ne t_j$，$1 \leq k_j \leq 3000$）。

输出 $q$ 行，第 $j$ 行输出从 $s_j$ 到 $t_j$ 的理想路径上的第 $k_j$ 个城市。如果不存在理想路径，或者 $k_j$ 超出了路径长度，则输出 '-1'。

由 ChatGPT 5 翻译