概要

この問題は、バリケードが設置されていない交差点のみを通る、交差点 \(1\) から交差点 \(N\) への最短経路の長さ（辺の数）を求める問題に帰着されます。

交差点 \(1\) を始点として、バリケードのある交差点を避けるように幅優先探索（BFS）を行い、交差点 \(N\) までの最短距離を計算することで、必要な道しるべの最小個数を求めることができます。

---

考察

1. 子猫の移動ルールと課題

子猫は「隣接する、機能している道しるべがある交差点のうち、最も番号が小さい交差点」へ移動します。 もし、子猫に特定のルートを通らせたいとき、進んでほしい交差点以外にも機能している道しるべが隣接していると、番号の大小関係によって意図しない交差点へ進んでしまい、誘導が失敗する可能性があります。

2. 最短経路の「ショートカットがない」性質の利用

この問題を解決する鍵は、「子猫がどの交差点にいるときも、隣接する機能している道しるべが『次に進むべき交差点』の1つだけである」 という状況を作ることです。

バリケードを避ける、交差点 \(N\) から \(1\) への最短パスを \(P = (N = v_0, v_1, v_2, \dots, v_d = 1)\) とします。このパス上の交差点 \(v_1, \dots, v_d\) の \(d\) 個の交差点にのみ道しるべを設置することを考えます。

子猫が \(v_i\) にいるとき、隣接する交差点の状況は以下のようになります。 - すでに通過した交差点 \(v_0, \dots, v_{i-1}\) の道しるべは、ルールによってすでに倒れており機能していません。 - 次に進むべき交差点 \(v_{i+1}\) の道しるべは機能しています。 - それ以降の交差点 \(v_{i+2}, \dots, v_d\) は、最短パスの性質上、\(v_i\) と隣接していません。（もし隣接していれば、そこをショートカットするより短いパスが存在することになり、最短パスであることに矛盾するためです）

したがって、子猫が \(v_i\) にいるとき、隣接する「機能している道しるべ」は \(v_{i+1}\) のただ1つ になります。 選択肢が1つしかないため、交差点の番号の大小に関わらず、子猫は確実に \(v_{i+1}\) へと進みます。

3. 最小個数の結論

最短パスに沿って道しるべを配置すれば、道しるべの数は最短パスの辺の数 \(d\)（＝移動先の交差点の数）になります。これより少ない個数で交差点 \(1\) に誘導することは不可能なため、この \(d\) が求める最小個数となります。

---

アルゴリズム

バリケードのない交差点のみを通る、交差点 \(1\) から交差点 \(N\) への最短距離を幅優先探索（BFS）で求めます。

1. 初期化:

   • 各交差点への最短距離を記録する配列 dist を \(-1\) で初期化します。
   • スタート地点である交差点 \(1\) の距離を dist[1] = 0 とし、キューに \(1\) を追加します。
   • バリケードがある交差点を高速に判定できるように、サイズ \(N+1\) の配列 barricades で管理します。

2. 探索 (BFS):

   • キューから交差点 \(u\) を取り出します。\(u = N\) に達した場合は、そこで探索を終了します。
   • \(u\) に隣接する各交差点 \(v\) について、以下を満たす場合に dist[v] = dist[u] + 1 と更新し、\(v\) をキューに追加します。
     • \(v\) にバリケードが設置されていない（barricades[v] == False）
     • \(v\) が未訪問である（dist[v] == -1）

3. 出力:

   • dist[N] の値を出力します。もしキューが空になっても交差点 \(N\) に到達できなかった場合、dist[N] は \(-1\) のままとなり、誘導不可能として正確に \(-1\) が出力されます。

---

計算量

• 時間計算量: \(O(N + M)\)
  • グラフのすべての頂点（交差点）と辺（道路）を最大1回ずつ探索するため、時間制限に対して十分に高速に動作します。
• 空間計算量: \(O(N + M)\)
  • 隣接リストの表現に \(O(N + M)\)、距離配列 dist やバリケードの有無を記録する配列に \(O(N)\) のメモリを使用します。

---

実装のポイント

• 高速な入出力: Pythonでは入力の数が多くなると input() の呼び出しオーバーヘッドが大きくなります。sys.stdin.read().split() を用いてすべての入力を一度に取得し処理することで、実行時間を大幅に短縮できます。

• バリケードの判定: 探索中に「バリケードがあるか」を毎回 \(O(1)\) で判定できるように、あらかじめ barricades を boolean 配列として構築しておくことが重要です。

  ソースコード

import sys
from collections import deque

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # 隣接リストの構築
    adj = [[] for _ in range(N + 1)]
    idx = 3
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        adj[u].append(v)
        adj[v].append(u)
        idx += 2
        
    # バリケード情報の記録
    barricades = [False] * (N + 1)
    for _ in range(K):
        b = int(input_data[idx])
        barricades[b] = True
        idx += 1
        
    # BFSによる1からNへの最短距離の計算
    dist = [-1] * (N + 1)
    queue = deque([1])
    dist[1] = 0
    
    while queue:
        u = queue.popleft()
        if u == N:
            break
        for v in adj[u]:
            if not barricades[v] and dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
                
    print(dist[N])

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。