提出 #58961442

---

ソースコード 拡げる

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

// #define int long long
using ll = long long;
using P = pair<int, int>;
template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
template<class T> using max_heap = priority_queue<T, std::vector<T>>;

#define LOG(variable) cerr << #variable":\t" << (variable) << "\n"
#define LOGCON(i, container) for(size_t (i) = 0; (i) < (container).size(); ++(i)) cerr << (i) << ":\t" << (container)[(i)] << "\n"
#define REP(i, n) for (long long i = 0; i < (n); ++i)
#define REPS(i, r, n) for (long long i = (r); i < (n); ++i)
#define REPR(i, n) for(long long i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(long long i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))

template<class T = int> T in() {T a; cin >> a; return a;}
template <typename T>
bool chmax(T &a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

// dis_map has to be empty
void bfs(unordered_map<int, vector<int>> &edges, unordered_map<int, int> &dis_map) {
    queue<P> que;
    que.push(P(1, 0));
    dis_map[1] = 0;
    while (que.size()) {
        int curr, dis;
        tie(curr, dis) = que.front(); que.pop();

        if (edges.find(curr) == edges.end()) continue;

        REPOBJ(next_itr, edges[curr]) {
            if (dis_map.find(*next_itr) != dis_map.end()) continue;

            dis_map[*next_itr] = dis + 1;
            que.push(P(*next_itr, dis + 1));
        }
    }
}

#define INF 20000000

/***** MAIN *****/
signed main() {
    int N, M; cin >> N >> M;
    unordered_map<int, vector<int>> edges, r_edges;
    REP(i, M) {
        int a, b; cin >> a >> b;
        if (edges.find(a) == edges.end()) edges[a] = vector<int>();
        edges[a].emplace_back(b);

        if (r_edges.find(b) == r_edges.end()) r_edges[b] = vector<int>();
        r_edges[b].emplace_back(a);
    }

    unordered_map<int, int> dis_from_f, dis_to_f;
    bfs(edges, dis_from_f);
    bfs(r_edges, dis_to_f);

    int ans = INF;
    REPS(i, 2, N + 1) {
        // Unreachable from 1
        if (dis_from_f.find(i) == dis_from_f.end()) continue;
        // Unreachable to 1
        if (dis_to_f.find(i) == dis_to_f.end()) continue;

        chmin(ans, dis_from_f[i] + dis_to_f[i]);
    }

    if (ans == INF) {
        cout << -1;
    } else {
        cout << ans;
    }
    cout << "\n";
    return 0;
}
/***** MAIN *****/

提出情報

ジャッジ結果