異常コーナーケース祭りのやばい問題だった

問題へのリンク

問題概要

頂点数 $N$ 、辺数 $M$ の連結な単純無向グラフが与えられる。このグラフの頂点 $S, T$ にそれぞれ駒 $A, B$ が置いてある。次の操作を繰り返す。

駒 $A, B$ のうちの一方を選ぶ
選んだ駒を隣接する頂点のいずれかに動かす（ただし、他方の駒のある頂点には移動できない）

操作を繰り返して、頂点 $S, T$ にそれぞれ駒 $B, A$ が置いてある状態にしたい。これを実現するための操作回数の最小値を求めよ（不可能な場合は -1）。

制約

$2 \le N \le 2 \times 10^{5}$

考えたこと

まず、パスグラフでは実現不可能で、それ以外のグラフでは実現可能であることはすぐにわかる。実現可能であるとき、おおまかには次の 3 通りのパターンが考えられた。

パターン 1：shortest path と second shortest path をそれぞれ使う
パターン 2：shortest path の内点であって次数 3 の頂点がある場合に、2 手を消費してすれ違いをする
パターン 3：shortest path 外にある S, T から最も近い次数 3 の頂点に行き、その場所ですれ違いをする

これで解けたかと思われたが、ここからの WA ラッシュがヤバかった。特にパターン 1 で重大な考察漏れがあった。second shortest path を求めるつもりで Dijkstra 法を回したところ、求められたのは second shortest walk だった。

たとえば、次の入力ケースを考える。

つまりサイクルだ。この場合には、

shortest path：1 - 2
second shortest path：1 - 5 - 4 - 3 - 2

である。これら 2 つのパスを使うのが最適で、答えは 5 手にならないとおかしいが、僕のプログラムは 4 手と返してきた。

理由は、プログラムで求めたつもりの second shortest path が "1 - 2 - 3 - 2" となっていて、実際には second shortest path ではなく、second shortest walk だったのだ。この walk では、shortest path とすれ違うことができない。

よって、ここから「shortest path とすれ違えるような path のうち、最短であるもの」を求めようとする戦いが始まった。来た辺を引き返してはいけないという制約を入れてみるなど、色々試したがどれも上手くいかなかった。やりたいことは

shortest path 上の辺を 1 本ずつ除去して、
残ったグラフ上での shortest path を求めていき、
それらの中で最短のものを見つける

というようなものだった。これを現実的な計算時間で求める方法は思いつけなかったので、方針転換する。

second shortest walk が、shortest path よりも 2 以上長い場合を分離する

shortest path の長さを $K$ 、second shortest walk の長さを $L$ とする。

$L \le K + 1$ である場合には、 $K + L$ が答えである。なぜなら、second shortest walk が shortest path と 1 差以下である場合には、second shortest walk は上に挙げたような変なものにはならないからだ。

以降、 $L \ge K + 2$ としよう。この場合は shortest path が一意に定まることに留意する。このとき、次のように分けて考えることができる。

shortest path の内点であって、次数 3 の頂点がある場合：答えは $2K + 2$ である
shortest path の内点の次数がすべて 2 である場合

前者については、 $2K + 2$ 以上要することは自明 ( $L \ge K + 2$ の場合を考えているので) で、それを実際に達成できることから示せる。

shortest path が唯一で、内点の次数がすべて 2 のとき

この場合は、shortest path の枝分かれがないことから、さらに次の 2 つの方法に綺麗に分けることができる！

一方の駒のみが shortest path の辺をすべて使い、他方の駒は shortest path の辺を全く使わない方法
両方の駒が shortest path の辺をすべて使う方法

前者については、もとのグラフから shortest path の辺をすべて除去した上で、もう一度 S-T 間の shortest path を求める。その長さを $D$ とすると、操作回数の最小値は $K + D$ となる。

shortest path の辺を 1 辺ずつ除去して shortest path を求める方法は思いつけなかったが、shortest path 上に枝分かれがない場合に絞ることで、まとめてすべて除去できる状況にできたのがポイントだった。

後者については、 $S, T$ のいずれかから最も近い「次数 3 の頂点」への距離を $d$ として、操作回数の最小値は $2K + 4(d+1)$ となる。

まとめ

shortest path の長さを $K$ とし、second shortest walk の長さを $L$ とする。

パスグラフの場合は -1
そうでなく、 $L \le K + 1$ の場合は、答えは $K + L$
そうでなく、shortest path 上に次数 3 の頂点がある場合は、答えは $2K + 2$
そうでない場合は、以下のうちの最小値:
- shortest path の辺をすべて除外してできるグラフの $S$ - $T$ 間の shortest path の長さを $D$ として、操作回数 $K + D$
- $S, T$ のいずれかから、最も近い次数 3 頂点への距離を $d$ として、操作回数 $2K + 4(d+1)$

コード

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

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

template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }

using pint = pair<int, int>;
using pll = pair<long long, long long>;
using vll = vector<long long>;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using int128 = __int128;
using u128 = unsigned __int128;
template <class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define ALL(x) x.begin(), x.end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl


using Graph = vector<vector<int>>;
const int INF = 1<<26;

int main() {
    int N, M, S, T, u, v;
    cin >> N >> M >> S >> T;
    S--, T--;
    Graph G(N);
    REP(i, M) {
        cin >> u >> v, u--, v--;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    // パスグラフを判定
    int one = 0, two = 0;
    for (int v = 0; v < N; v++) {
        if (G[v].size() == 1) one++;
        else if (G[v].size() == 2) two++;
    }
    if (one == 2 && two == N-2) {
        cout << -1 << endl;
        return 0;
    }

    // shortest path と、second shortest walk を求める
    auto dijkstra = [&](int start, int goal, set<pint> ng) -> array<vector<int>, 3> {
        vector<int> dp1(N, INF), dp2(N, INF), prev(N, -1);
        min_priority_queue<array<int,3>> que;
        dp1[start] = 0;
        que.push({0, start, -1});
        while (!que.empty()) {
            auto [dis, v, p] = que.top();
            que.pop();
            if (dis > dp2[v]) continue;
            for (auto v2 : G[v]) {
                if (ng.count(pint(v, v2)) || ng.count(pint(v2, v))) continue;
                int before = dp1[v2];
                if (chmin(dp1[v2], dis + 1)) {
                    que.push({dp1[v2], v2, v});
                    prev[v2] = v;
                    dp2[v2] = before;
                } else if (chmin(dp2[v2], dis + 1)) {
                    que.push({dp2[v2], v2, v});
                }
            }
        }
        return {dp1, dp2, prev};
    };
    auto [dp1, dp2, prev] = dijkstra(S, T, set<pint>());

    // len(second shortest walk) <= len(shortest path) + 1 の場合は早々と処理
    if (dp2[T] <= dp1[T] + 1) {
        cout << dp1[T] + dp2[T] << endl;
        return 0;
    }

    // S-T shortest path 上に枝分かれがある場合
    vector<int> path({T});
    int cur = T;
    while (cur != S) {
        cur = prev[cur];
        path.push_back(cur);
    }
    for (int i = 1; i+1 < path.size(); i++) {
        int v = path[i];
        if (G[v].size() > 2) {
            cout << dp1[T] * 2 + 2 << endl;
            return 0;
        }
    }
    
    // second shortest walk - shortest path >= 2 かつ shotest path 上に分岐がないとき
    // この場合は、S-T shortest path は一方の駒しか使わない
    // よって、S-T shortest path は除外した状態での最短路を求める
    set<pint> ng;
    for (int i = 0; i+1 < path.size(); i++) ng.insert(pint(path[i], path[i+1]));
    auto [dpS1, dpS2, prevS] = dijkstra(S, T, ng);
    auto [dpT1, dpT2, prevT] = dijkstra(T, S, ng);
    int res1 = dp1[T] + dpS1[T];  // その 2 つのパスを使うのが候補

    // S, T から離れたところの分岐を活用する場合
    int min_dist = INF, res2 = INF;
    for (int v = 0; v < N; v++) {
        if (G[v].size() > 2) chmin(min_dist, min(dpS1[v], dpT1[v]));
    }
    chmin(res2, dp1[T] * 2 + (min_dist + 1) * 4);

    cout << min(res1, res2) << endl;
}