P2296 寻找道路

#include <bits/stdc++.h>

using namespace std;

const int maxn = 10005;

set<int> to[maxn];

queue<int> q;int s, t;int n, m;set<int> to2[maxn];

int dist[maxn], used[maxn], dist2[maxn];

int main() {

//    freopen("input.in", "r", stdin);

    cin >> n >> m;

    for(int i = 1; i <= m; i++) {

        int x, y;

        cin >> x >> y;

        to[x].insert(y);

        to2[y].insert(x);

    }

    cin >> s >> t;

    //-----------------

    q.push(t);

    memset(dist2, -1, sizeof(dist2));

    dist2[t] = 0;

    memset(used, 0, sizeof(used));

    used[t] = 1;

    while(!q.empty()) {

        int x = q.front();

        q.pop();

        set<int>::iterator it;

        for(it = to2[x].begin(); it != to2[x].end(); it++) {

            if(!used[*it]) {

                dist2[*it] = dist2[x] + 1;

                used[*it] = 1;

                q.push(*it);

            }

        }

    }

    memset(used, 0, sizeof(used));

    for(int i = 1; i <= n; i++) {

        if(dist2[i] == -1) {

            set<int>::iterator it;

            for(it = to2[i].begin(); it!=to2[i].end(); it++) {

                used[*it] = 1;

            }

        }

    }

    //-----------------

    memset(dist, -1, sizeof(dist));

    dist[s] = 0;

    q.push(s);

    used[s] = 1;

    while(!q.empty()) {

        int x = q.front();

        q.pop();

        set<int>::iterator it;

        for(it = to[x].begin(); it != to[x].end(); it++) {

            if(!used[*it]) {

                dist[*it] = dist[x] + 1;

                used[*it] = 1;

                q.push(*it);

            }

        }

    }

    cout << dist[t];

}