题意：给定一张有向图，询问 \(s, t\) 两点间字典序最小路径上的第 \(k\) 个结点。
首先要验证 \(s, t\) 间是否连通，所以建反图，枚举 \(1 \sim n\)，跑 dfs。这部分时间复杂度 \(\mathcal O(n^2)\)。
确定了哪些点跟 \(t\) 连通后，\(s\) 到 \(t\) 的路径就固定了，\(s\) 只能走终点能到 \(t\) 的且字典序最小的路，重新建图后再跑 dfs，因为起点有多个，时间复杂度 \(\mathcal O(n^3)\)，有点超了，考虑优化。
前面枚举的是终点，也就是说终点是确定的，于是再建反图，在 \(t\) 跑 dfs 即可，路径上第 \(k\) 个结点的询问用栈统计下就好，时间复杂度 \(\mathcal O(n^2)\)。
总时间复杂度 \(\mathcal O(n^2)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 3e3 + 10, Q = 4e5 + 10;
int n, m, q, ans[Q];
int top, stk[N];
bool vis[N];
struct Node {
int s, t, k;
} ask[Q];
vector<int> G[N], invG[N], H[N], qs[N], qt[N];
inline void add(int u, int v) {G[u].emplace_back(v), invG[v].emplace_back(u);}
void dfs1(int u) {
vis[u] = 1;
for (int v : invG[u]) if (!vis[v]) dfs1(v);
}
void dfs2(int u) {
vis[stk[++top] = u] = 1;
for (int i : qs[u]) if (ask[i].k <= top) ans[i] = stk[top - ask[i].k + 1];
for (int v : H[u]) if (!vis[v]) dfs2(v);
top--;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> q;
for (int i = 1, u, v; i <= m; i++) cin >> u >> v, add(u, v);
for (int i = 1; i <= n; i++) sort(G[i].begin(), G[i].end());
for (int i = 1; i <= q; i++) {
cin >> ask[i].s >> ask[i].t >> ask[i].k;
qt[ask[i].t].emplace_back(i);
}
fill(ans + 1, ans + q + 1, -1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) H[j].clear(), qs[j].clear();
for (int j : qt[i]) qs[ask[j].s].emplace_back(j);
memset(vis, 0, sizeof(vis)), dfs1(i);
for (int j = 1; j <= n; j++) if (vis[j] && j != i) for (int v : G[j]) if (vis[v]) {H[v].emplace_back(j); break;}
memset(vis, 0, sizeof(vis)), dfs2(i);
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
return 0;
}