概要

この問題は、通行可能な道路のみを使って、街 \(1\) から街 \(N\) までの最短経路（通る道路の本数の最小値）を求める問題です。

考察

最短経路を求める問題ですが、以下の点がポイントになります。

• 重みなしグラフの最短経路: すべての道路の「長さ」は \(1\) とみなせます。このような「辺の重みがすべて等しいグラフ」において、ある頂点から別の頂点への最短距離を求めるには、幅優先探索 (BFS) が最適です。
• 通行止めの扱い: \(S_i = 0\) の道路は移動に使うことができません。したがって、グラフを構築する段階でこれらの道路を無視し、\(S_i = 1\) の道路のみを隣接リストに追加することで、単純な最短経路問題に帰着させることができます。
• 制約と計算量: 街の数 \(N\) と道路の数 \(M\) はともに \(2 \times 10^5\) 程度です。BFS を用いると \(O(N + M)\) の計算量で解くことができるため、制限時間内に十分間に合います。

アルゴリズム

幅優先探索 (BFS) によるアプローチ

1. グラフの構築: \(S_i = 1\) である道路の情報のみを使って、隣接リスト adj を作成します。
2. 初期化: 街 \(1\) から各街への最短距離を保持する配列 dist を用意し、すべての要素を \(-1\)（未訪問であることを示す）で初期化します。スタート地点である街 \(1\) の距離は dist[1] = 0 とします。
3. 探索:
   • 街 \(1\) をキューに追加します。
   • キューが空になるまで、以下の処理を繰り返します。
     1. キューの先頭から現在の街 \(u\) を取り出す。
     2. 街 \(u\) に隣接する街 \(v\) を順番に調べる。
     3. もし街 \(v\) が未訪問 (dist[v] == -1) ならば、dist[v] = dist[u] + 1 と更新し、街 \(v\) をキューの末尾に追加する。
4. 出力: dist[N] の値を出力します。もし一度も街 \(N\) に到達できず、値が \(-1\) のままだった場合は、問題文の指示通り \(-1\) を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 隣接リストの構築に \(O(M)\)、BFS による探索で各頂点を最大 \(1\) 回、各辺を最大 \(2\) 回（双方向のため）走査するため、全体で \(O(N + M)\) となります。
• 空間計算量: \(O(N + M)\)
  • 隣接リストの保持に \(O(N + M)\)、距離配列 dist に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, M\) が大きいため、Python では sys.stdin.read().split() を使って一括で入力を読み込むことで実行時間を短縮しています。

• 効率的なキュー: collections.deque を使用することで、キューの先頭要素の取り出し (popleft) を \(O(1)\) で行うことができます。Python の標準リストの pop(0) は \(O(N)\) かかるため、競技プログラミングでは deque の使用が推奨されます。

  ソースコード

import sys
from collections import deque

def solve():
    # 標準入力から全データを読み込み、スペースで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 街の数 N と道路の数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 通行可能な道路のみを管理する隣接リストを作成
    adj = [[] for _ in range(N + 1)]
    
    # 道路情報のパース
    # input_data[0]はN, input_data[1]はMなので、各道路の情報はインデックス2から始まる
    for i in range(M):
        u = int(input_data[3 * i + 2])
        v = int(input_data[3 * i + 3])
        s = int(input_data[3 * i + 4])
        
        # S_i = 1 のときのみ、その道路は通行可能
        if s == 1:
            adj[u].append(v)
            adj[v].append(u)
            
    # 街1からの最短距離を保持する配列。-1で初期化（未訪問）
    dist = [-1] * (N + 1)
    dist[1] = 0
    
    # BFS（幅優先探索）のためのキュー
    queue = deque([1])
    
    while queue:
        u = queue.popleft()
        
        # 目的地である街Nに到達した場合
        if u == N:
            print(dist[N])
            return
            
        # 隣接する街を探索
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
                
    # 全ての到達可能な街を探索しても街Nに辿り着けなかった場合
    print(-1)

if __name__ == '__main__':
    solve()

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