概要

通行可能な道路（\(S_i = 1\)）のみを使って、街 \(1\) から街 \(N\) への最短経路（通る道路の本数が最小）を求める問題です。典型的な重みなしグラフの最短経路問題であり、BFS（幅優先探索）で解くことができます。

考察

重要な気づき

• 各道路の「長さ」はすべて \(1\) です（重みなしグラフ）。
• 通行止め（\(S_i = 0\)）の道路はそもそも使えないので、最初からグラフに含めなければよいです。
• 通行可能な道路だけで構成されたグラフ上で、街 \(1\) から街 \(N\) への最短距離を求める問題に帰着します。

なぜ BFS なのか

• 重み付きグラフであればダイクストラ法などが必要ですが、本問ではすべての辺の重みが \(1\)（均一）です。
• 重みが均一なグラフの最短経路は BFS で \(O(N + M)\) で求められます。
• 例えば DFS（深さ優先探索）では最短経路が保証されないため、BFS を使う必要があります。

具体例

街が 4 つ、道路が以下のような場合を考えます：

• 道路 1: 街 \(1\) ↔ 街 \(2\)（通行可能）
• 道路 2: 街 \(2\) ↔ 街 \(4\)（通行止め）
• 道路 3: 街 \(1\) ↔ 街 \(3\)（通行可能）
• 道路 4: 街 \(3\) ↔ 街 \(4\)（通行可能）

通行可能な道路だけを使うと、\(1 \to 3 \to 4\) の経路で道路 \(2\) 本が最短となります。\(1 \to 2\) の先は街 \(4\) へ行けない（道路 2 が通行止め）ため、この迂回路を選ぶ必要があります。

アルゴリズム

1. グラフの構築: 入力を読み込み、\(S_i = 1\)（通行可能）の道路のみを隣接リストに追加します。
2. BFS の実行: 街 \(1\) を始点として BFS を行い、各街への最短距離を求めます。
   • キュー（FIFO）を使い、始点からの距離が小さい順に街を探索します。
   • 各街は最初に訪問したときの距離が最短距離となるため、一度訪問した街は再訪問しません。
3. 結果の出力: 街 \(N\) への最短距離を出力します。街 \(N\) に到達できなかった場合は \(-1\) を出力します。

BFS の動作イメージ：

距離 0: 街1 をキューに入れる
距離 1: 街1 の隣接頂点をキューに入れる
距離 2: 距離1 の頂点の隣接頂点をキューに入れる
...（街N に到達するまで続ける）

計算量

• 時間計算量: \(O(N + M)\)
  • グラフの構築に \(O(M)\)、BFS に \(O(N + M)\)（各頂点・各辺を高々 1 回ずつ処理）
• 空間計算量: \(O(N + M)\)
  • 隣接リストに \(O(N + M)\)、距離配列とキューに \(O(N)\)

実装のポイント

• 通行止めの道路をフィルタリング: グラフ構築時に \(S_i = 1\) の道路のみを追加することで、BFS 中に条件分岐する必要がなくなります。

• 早期終了: BFS 中に街 \(N\) に到達した時点で即座に答えを出力して終了しています。BFS では最初に到達した時点の距離が最短であることが保証されるため、これで正しい結果が得られます。

• deque の使用: Python では collections.deque を使うことで、キューの先頭からの取り出し（popleft()）を \(O(1)\) で行えます。リストの pop(0) は \(O(N)\) かかるため、必ず deque を使いましょう。

  ソースコード

from collections import deque

def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, s = map(int, input().split())
        if s == 1:
            graph[u].append(v)
            graph[v].append(u)
    
    # BFS from 1 to N
    dist = [-1] * (N + 1)
    dist[1] = 0
    queue = deque([1])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if dist[nxt] == -1:
                dist[nxt] = dist[node] + 1
                if nxt == N:
                    print(dist[N])
                    return
                queue.append(nxt)
    
    print(dist[N])

main()

---

この解説は claude4.6opus-thinking によって生成されました。