概要

この問題は、「バリケードがある交差点を通らずに、交差点 \(N\) から交差点 \(1\) まで行く最短経路の長さ」を求める問題に言い換えられます。

答えは、バリケードの交差点を除いたグラフ上での \(N\) から \(1\) への最短距離です。

考察

道しるべを置いた交差点にだけ子猫は移動できます。

つまり、子猫がある交差点へ移動するためには、その交差点に道しるべが必要です。

例えば、次のような経路で誘導したいとします。

\[ N \rightarrow a \rightarrow b \rightarrow 1 \]

このとき、道しるべは \(a, b, 1\) に置く必要があります。

したがって、この経路で必要な道しるべの数は、通る道路の本数と同じ \(3\) 個です。

特に、交差点 \(1\) に移動するためにも、交差点 \(1\) に道しるべが必要です。

---

重要な観察は次の通りです。

任意の成功する誘導には、その移動回数以上の道しるべが必要

子猫が実際に

\[ N = v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_L = 1 \]

と移動したとします。

各 \(v_i \ (i \geq 1)\) には、移動するために道しるべが必要です。

また、交差点 \(1\) 以外の道しるべは到着後に倒れるため、同じ交差点へ何度も移動することはできません。

よって、少なくとも \(L\) 個の道しるべが必要です。

この移動列は、バリケードのない交差点だけを通る経路なので、\(N\) から \(1\) への最短距離を \(D\) とすると、

\[ D \leq L \]

です。

したがって、必要な道しるべの数は少なくとも \(D\) 個です。

---

最短経路に沿って道しるべを置けば十分

逆に、バリケードを避けた最短経路を

\[ N = v_0 \rightarrow v_1 \rightarrow \cdots \rightarrow v_D = 1 \]

とします。

このとき、\(v_1, v_2, \ldots, v_D\) に道しるべを置けば、道しるべの数は \(D\) 個です。

子猫は現在地に隣接する「機能している道しるべ」のうち、番号が最も小さい交差点へ移動します。

一見すると、番号の大小によって予定と違う方向へ行きそうに見えます。

しかし、最短経路上では、現在地 \(v_i\) から経路上の先の交差点 \(v_j \ (j > i + 1)\) に直接道路があることはありません。

もしそのような道路があれば、

\[ v_i \rightarrow v_{i+1} \rightarrow \cdots \rightarrow v_j \]

という部分を、直接

\[ v_i \rightarrow v_j \]

に置き換えることで、より短い経路が作れてしまい、最短経路であることに矛盾します。

したがって、最短経路上で現在地から進める機能中の道しるべは、基本的に次の交差点 \(v_{i+1}\) だけです。

前の交差点の道しるべはすでに倒れているため、子猫は最短経路に沿って進み、最後に交差点 \(1\) へ到着できます。

---

以上より、答えは単に

バリケードの交差点を通れないものとして、\(N\) から \(1\) への最短距離

になります。

素朴に「どの交差点に道しるべを置くか」を全探索すると、各交差点について置く・置かないの選択があり、最大で \(2^N\) 通りになってしまうため到底間に合いません。

そこで、グラフの最短距離を BFS で求めます。

アルゴリズム

グラフはすべての道路の長さが等しい無重みグラフです。

そのため、最短距離は BFS（幅優先探索）で求められます。

手順は以下の通りです。

1. グラフを隣接リストで管理する
2. バリケードがある交差点を blocked 配列で記録する
3. 交差点 \(N\) から BFS を開始する
4. 隣接先がバリケードなら無視する
5. まだ訪問していない交差点なら距離を更新してキューに入れる
6. 最後に dist[1] を出力する
   • 到達できなければ dist[1] = -1 のままなので、そのまま \(-1\) を出力する

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• バリケードがある交差点には道しるべを置けないため、BFS でもその交差点には進まないようにします。

• 交差点 \(1\) と交差点 \(N\) にはバリケードがないことが保証されています。

• dist[v] = -1 を「未訪問」として扱います。

• BFS の開始地点は子猫の出発地点である交差点 \(N\) です。

  ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    vector<vector<int>> G(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    vector<bool> blocked(N + 1, false);
    for (int i = 0; i < K; i++) {
        int b;
        cin >> b;
        blocked[b] = true;
    }

    vector<int> dist(N + 1, -1);
    queue<int> q;

    dist[N] = 0;
    q.push(N);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : G[v]) {
            if (blocked[to]) continue;
            if (dist[to] != -1) continue;

            dist[to] = dist[v] + 1;
            q.push(to);
        }
    }

    cout << dist[1] << '\n';

    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。