#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 3005, INF = 0x3f3f3f3f;
int n, m, q, f[N][12];
bool vis[N];
struct Edge {
int to;
Edge *next;
Edge () {}
Edge (int to, Edge *next) : to(to), next(next) {}
}*head[N], pool[N << 1], *pis = pool;
void Min (int &x, int y) { if (x > y) x = y; }
int fr[N], tt[N], ins[N];
void Dfs (int x) {
vis[x] = 1;
for (Edge *now = head[x]; now; now = now -> next) {
Min(fr[now -> to], x);
if (!vis[now -> to]) Dfs(now -> to);
}
}
void Dfs2 (int x) {
if (tt[x] != INF) return ;
if (fr[x] == INF || ins[fr[x]]) { tt[x] = -1; return ; }
ins[x] = 1;
Dfs2(fr[x]);
tt[x] = tt[fr[x]] == -1 ? -1 : tt[fr[x]] + 1;
ins[x] = 0;
}
struct E { int x, y, k, id; bool operator < (const E &rhs) const { return y < rhs.y; } }e[400005];
int i, ans[400005];
int main () {
scanf(“%d%d%d”, &n, &m, &q);
for (int i = 1, x, y; i <= m; ++i) {
scanf(“%d%d”, &x, &y);
head[y] = new (pis++) Edge(x, head[y]);
}
for (int i = 0; i < q; ++i) scanf(“%d%d%d”, &e[i].x, &e[i].y, &e[i].k), e[i].id = i;
sort(e, e + q);
for (int x, y, k, lay = -1, ans, w = q; w–; ) {
x = e[w].x; y = e[w].y; k = e[w].k;
if (lay != y) {
memset(vis, 0, sizeof vis), memset(fr, 0x3f, sizeof fr), memset(tt, 0x3f, sizeof tt), Dfs(y), tt[y] = 1;
for (i = 1; i <= n; ++i) Dfs2(i), f[i][0] = fr[i];
for (int j = 1; j < 12; ++j) for (i = 1; i <= n; ++i) if (f[i][j – 1] != INF) f[i][j] = f[f[i][j – 1]][j – 1];
}
if (fr[x] == 0x3f3f3f3f) ::ans[e[w].id] = -1;
else {
if (tt[x] == -1 || tt[x] < k) ::ans[e[w].id] = -1;
else {
–k;
for (int j = 0; j < 12; ++j) if (k >> j & 1) x = f[x][j];
::ans[e[w].id] = x;
}
// for (i = 1; i < k && x != y; ++i) x = fr[x]; if (i != k) { ::ans[e[j].id] = -1; continue ; } ans = x;
// for (; i <= 3000 && x != y; ++i) x = fr[x];
// ::ans[e[j].id] = x != y ? -1 : ans;
}
lay = y;
}
for (int i = 0; i < q; ++i) printf(“%d\n”, ans[i]);
return 0;
}
, problem: (F) Cities Excursions Solution In C/C++. #include #include #include using namespace){kind=link}