一个看起来比较有用的小 trick。

ABC287Ex - Directed Graph and Query

其实相当于分步加入点，构成点导出子图。

Floyd 维护联通性来判断。

但是 Floyd 是 \(O(N^3)\) 的，非常慢。

那么拿 bitset 维护就能优化成 \(O(\dfrac{N^3}{w})\) 了。

这里枚举的 \(i\) 实际上是枚举的中转点（Floyd 循环中的 \(k\)）。

枚举 \(i\)，保证当前图上仅有点权 \(\le i\) 的点。

那么有，如果当前联通，则答案一定最小。

更新答案即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 10;
int n, m, q, st[N << 3], ed[N << 3], res[N << 3];
vector <int> g[N]; bitset <N> t[N];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> n >> m; for (int i = 1, u, v; i <= m; ++i)
        cin >> u >> v, t[u][v] = true;
    for (int i = 1; i <= n; ++i) t[i][i] = true;
    cin >> q; for (int i = 1; i <= q; ++i) cin >> st[i] >> ed[i];
    memset(res, -1, sizeof(res));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) if (t[j][i]) t[j] |= t[i];
        for (int j = 1; j <= q; ++j)
            if (res[j] == -1 && t[st[j]][ed[j]]) res[j] = max({st[j], ed[j], i});
    }
    for (int i = 1; i <= q; ++i) cout << res[i] << endl;
    return 0;
}