提出 #43363763

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
using Graph = vector<vector<pair<int, ll>>>;

template <class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    } else
        return false;
}

vector<ll> dijkstra(const Graph &G, int s) {
    int N = G.size();
    vector<ll> dist(N, INF);
    dist[s] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>
        que;
    que.push(make_pair(dist[s], s));
    while (!que.empty()) {
        int v = que.top().second;
        ll d = que.top().first;
        que.pop();
        if (d > dist[v]) continue;
        for (auto e : G[v]) {
            if (chmin(dist[e.first], dist[v] + e.second)) {
                que.push(make_pair(dist[e.first], e.first));
            }
        }
    }
    return dist;
}

int main() {
    int N1, N2, M;
    cin >> N1 >> N2 >> M;
    Graph G(N1 + N2);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back({b, 1});
        G[b].push_back({a, 1});
    }
    auto d1 = dijkstra(G, 0);
    auto d2 = dijkstra(G, N1 + N2 - 1);
    ll Md1 = 0, Md2 = 0;
    for (auto d : d1) {
        if (d == INF) continue;
        Md1 = max(Md1, d);
    }
    for (auto d : d2) {
        if (d == INF) continue;
        Md2 = max(Md2, d);
    }
    cout << Md1 + Md2 + 1 << endl;
    return 0;
}

提出情報

ジャッジ結果