概要

通行可能な道路（\(S_i=1\)）だけで作った無向グラフ上で、街 \(1\) から街 \(N\) までの最短辺数を求める問題です。
各道路のコストはすべて同じ（1本進むごとに1）なので、幅優先探索（BFS）で最短距離を求められます。

考察

この問題の本質は「最小で何本の道路を通るか」です。
道路1本ごとの重みがすべて同じなので、これはそのまま最短路問題（重みなしグラフ）になります。

重要な気づき

• \(S_i=0\) の道路は使えないので、最初からグラフに入れない。
• 残った道路はすべて同じコスト（1）。
• 重みなしグラフの最短距離は BFS で求まる。

素朴な方法が厳しい理由

• 「街1から行ける経路を全部試す」DFS/バックトラックは、経路数が爆発して現実的ではありません。
• 「同じ街や道路を何回通ってもよい」と書かれていますが、最短本数を求めるなら無駄な往復は不要です。
  BFS で最初に到達したときの距離が最小になります。

どう解決するか

• 通行可能な辺のみで隣接リストを作る。
• 街1を始点に BFS。
• dist[v] を「街1から街vへの最小本数」として管理する。
• 最後に dist[N] を出力（未到達なら -1）。

アルゴリズム

1. graph を長さ N+1 の隣接リストで用意する（街番号が1始まりのため）。
2. 各道路 \((u,v,s)\) を読み込み、s==1 のときだけ
   graph[u].append(v), graph[v].append(u) を行う（無向）。
3. 距離配列 dist を -1 で初期化し、dist[1]=0。
4. キューに 1 を入れて BFS 開始。
5. キューから cur を取り出し、未訪問の隣接頂点 nxt に対して
   dist[nxt] = dist[cur] + 1 としてキューに追加。
6. 探索後、dist[N] を出力する（到達不可なら -1 のまま）。

※ 提示コードでは cur == N になった時点で break しています。
BFSでは先に取り出されるほど距離が小さいため、この時点で最短距離は確定しており正しいです。

計算量

• 時間計算量: \(O(N + M)\)
  （各頂点・各辺を高々1回ずつ見るため）
• 空間計算量: \(O(N + M)\)
  （隣接リスト、距離配列、キュー）

実装のポイント

• 入力サイズが大きいので sys.stdin.readline を使うと高速です。

• 多重辺があっても問題ありません。BFS側で未訪問判定（dist[nxt] == -1）をするので正しく処理できます。

• 到達不能判定は dist[N] == -1 をそのまま使えます。

  ソースコード

import sys
from collections import deque

def main():
    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)

    dist = [-1] * (N + 1)
    q = deque([1])
    dist[1] = 0

    while q:
        cur = q.popleft()
        if cur == N:
            break
        nd = dist[cur] + 1
        for nxt in graph[cur]:
            if dist[nxt] == -1:
                dist[nxt] = nd
                q.append(nxt)

    print(dist[N])

if __name__ == "__main__":
    main()

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