Codeforces Round #333 (Div. 1) A. The Two Routes

問題

codeforces.com

解法

ごちゃごちゃ書いてますが, 一つのルートでは目的地まで距離 1 で行けて, もうひとつのルートでは距離 1 で行けないので, 何も考えず２つのルートの最短経路の最大値を取れば良いだけです。

struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

bool ok[444][444];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<edge> > G1(n), G2(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        ok[x][y] = ok[y][x] = true;
    }
    for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) {
        if (ok[i][j]) {
            G1[i].emplace_back(j, 1);
            G1[j].emplace_back(i, 1);
        } else {
            G2[i].emplace_back(j, 1);
            G2[j].emplace_back(i, 1);
        }
    }
    auto d1 = dijkstra(n, G1, 0);
    auto d2 = dijkstra(n, G2, 0);
    ll ans = max(d1[n-1], d2[n-1]);
    if (ans > LLONG_MAX/100) ans = -1;
    cout << ans << endl;
    return 0;
}