bitset 高速化を使う点は公式解説と同じですが、使い方が異なる解法です。また、GCC 拡張の機能を用います。

まず、以下の TLE コードを考えます。これは、すべての \(i,j\) に対する「頂点 \(i\) から頂点 \(j\) への経路のコストの最小値」を単純な DFS で求めるコードです。始点 \(i\) を固定した上で、変数 lim を \(i,i+1,\dots,N\) と順に設定しながら、「\(i\) から lim 以下の頂点のみを辿って到達可能な頂点の集合」を更新しています。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> G(n), rG(n);
    for (int i = 0; i < m; i++) {
        int a, b;
      	cin >> a >> b;
        --a, --b;
        G[a].push_back(b);
        rG[b].push_back(a);
    }
    int q;
    cin >> q;
    vector<int> s(q), t(q);
    for (int i = 0; i < q; i++) {
        cin >> s[i] >> t[i];
        --s[i], --t[i];
    }
    vector ans(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++) {
        vector<bool> seen(n);
        int lim = i;
        auto dfs = [&](auto &dfs, int u) -> void {
            seen[u] = true;
            ans[i][u] = lim + 1;
            for (int v : G[u]) {
                if (v > lim) continue;
                if (seen[v]) continue;
              	dfs(dfs, v);
            }
        };
        dfs(dfs, i);
        for (int j = i + 1; j < n; j++) {
            ++lim;
            for (int k : rG[j]) {
                if (seen[k]) {
                    dfs(dfs, j);
                    break;
                }
            }
        }
    }
    for (int i = 0; i < q; i++) cout << ans[s[i]][t[i]] << '\n';
}

上のコードの計算量は \(O(NM+Q)\) ですが、ボトルネックは以下の \(2\) 箇所です。

• 関数 dfs の中で、「今見ている頂点から出る辺」を全探索する所（\(30\) - \(34\) 行目）
• 新たに通れるようになる頂点について、「既に到達可能な頂点から辺を \(1\) 本たどってその頂点に到達できるか」を判定する所（\(39\) - \(44\) 行目）

後者は配列 seen と rG を bitset で持つことで高速化可能です。

前者については、「今見ている頂点から出る辺」のうち「lim 以下かつまだ到達していない頂点に伸びる辺」のみを探索することで、探索回数を \(O(N^2)\) に抑えることができます。これは bitset の _Find_first 関数を用いることで実現可能です。

以下のコードは上記の bitset 高速化を反映したものであり、実際に AC をとることができます。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<bitset<2010>> G(n), rG(n);
    for (int i = 0; i < m; i++) {
        int a, b;
      	cin >> a >> b;
        --a, --b;
        G[a][b] = 1;
        rG[b][a] = 1;
    }
    int q;
    cin >> q;
    vector<int> s(q), t(q);
    for (int i = 0; i < q; i++) {
        cin >> s[i] >> t[i];
        --s[i], --t[i];
    }
    vector ans(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++) {
        bitset<2010> seen;
        int lim = i;
        auto dfs = [&](auto &dfs, int u) -> void {
            seen[u] = true;
            ans[i][u] = lim + 1;
            while (true) {
                int v = (G[u] & (~seen))._Find_first();
                if (v > lim) break;
                dfs(dfs, v);
            }
        };
        dfs(dfs, i);
        for (int j = i + 1; j < n; j++) {
            ++lim;
            if ((seen & rG[j]).count()) dfs(dfs, j);
        }
    }
    for (int i = 0; i < q; i++) cout << ans[s[i]][t[i]] << '\n';
}