Submission

Score: 100

User: hmmm

Problemset: ย้อนศร

Language: cpp

Time: 0.461 second

Submitted On: 2025-01-09 17:01:08

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

const int INF = 1e9;

vector<pair<int, int>> graph[100005];
int dist[100005];

void zeroOneBFS(int start, int n) {
    deque<int> dq;
    fill(dist, dist + n + 1, INF);
    dist[start] = 0;
    dq.push_front(start);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (auto e: graph[u]) {
        	auto v=e.first;
        	auto weight=e.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                if (weight == 0) {
                    dq.push_front(v);
                } else {
                    dq.push_back(v);
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(v, 0);
        graph[v].emplace_back(u, 1);
    }

    int q;
    cin >> q;

    while (q--) {
        int a, b;
        cin >> a >> b;

        zeroOneBFS(a, n);

        if (dist[b] == INF) {
            cout << '0'<< '\n';
        } else {
            cout << dist[b] << '\n';
		}
    }

    return 0;
}