概要

通行可能な道路（\(S_i=1\)）だけを残したグラフを考えると、この問題は「街 \(1\) から街 \(N\) までの最短距離（辺数）」を求める問題になります。
道路 1 本を通るごとのコストがすべて同じ \(1\) なので、幅優先探索（BFS）で最小本数を求められます。

考察

まず重要なのは、通行止めの道路は最初から存在しないものとして無視してよいという点です。
問題文では「同じ街や同じ道路を複数回通ってもよい」とありますが、最小本数を求めるなら、無駄に行ったり来たりする必要はありません。

例えば、

• \(1 \to 2 \to 3 \to N\) で行けるなら 3 本
• 途中で \(2 \to 1 \to 2\) のような寄り道をすると本数が増えるだけ

なので、結局は 通行可能な道路だけからなる無向グラフ上での最短路問題です。

素朴な方法ではどうなるか

街 \(1\) から行ける経路を全部試して最短のものを探す、という方法は現実的ではありません。
道の選び方は非常に多く、\(N, M \le 2 \times 10^5\) という制約では全探索は間に合いません。

どう解決するか

この問題では、どの道路を通っても「1 本進む」というコストは одинаковく、すべて重み \(1\) の辺だと考えられます。
このようなグラフで最短距離を求める定番手法が 幅優先探索（BFS） です。

BFS では、

• 距離 0 の頂点（街 1）から始める
• そこから 1 本で行ける街
• 次に 2 本で行ける街
• 次に 3 本で行ける街

というように、距離の小さい順に探索できます。
したがって、最初に街 \(N\) に到達したときの距離が最小本数になります。

アルゴリズム

1. 隣接リスト g を用意する。
2. 入力された各道路について、\(S_i=1\) のときだけ無向辺として g[U_i] と g[V_i] に追加する。
3. 配列 dist を用意し、各街への最短本数を管理する。
   初期値は「未訪問」を表す -1 とし、dist[1] = 0 とする。
4. キューを使って BFS を行う。
   • キューから街 x を取り出す
   • x から通行可能な隣接街 y を見る
   • まだ未訪問なら dist[y] = dist[x] + 1 としてキューに入れる
5. 探索終了後、
   • dist[N] が -1 なら到達不可能なので -1
   • そうでなければその値が答え

具体例

例えば、通行可能な道路だけを見ると

• \(1 \leftrightarrow 2\)
• \(2 \leftrightarrow 4\)
• \(1 \leftrightarrow 3\)
• \(3 \leftrightarrow 4\)

となっていたとします。

このとき BFS では

• dist[1] = 0
• dist[2] = 1, dist[3] = 1
• dist[4] = 2

となるので、答えは \(2\) です。
実際、\(1 \to 2 \to 4\) または \(1 \to 3 \to 4\) で 2 本です。

計算量

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

BFS では各街を高々 1 回キューに入れ、各通行可能な道路も高々 2 回（両端から）見るだけなので、全体で線形時間です。

実装のポイント

• \(S_i=0\) の道路はグラフに入れないのがポイントです。これで問題がそのまま普通の最短路問題になります。

• 道路は双方向なので、g[u].append(v) と g[v].append(u) の両方を行います。

• dist を -1 で初期化すると、「未訪問」と「最短距離」を同じ配列で管理できて便利です。

• 多重辺があっても問題ありません。BFS ではすでに訪問済みなら無視されるため、正しく動作します。

• 入力サイズが大きいため、実装では sys.stdin.buffer.read() を使って高速に読み込んでいます。

  ソースコード

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m = data[0], data[1]
    g = [[] for _ in range(n + 1)]

    idx = 2
    for _ in range(m):
        u = data[idx]
        v = data[idx + 1]
        s = data[idx + 2]
        idx += 3
        if s == 1:
            g[u].append(v)
            g[v].append(u)

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

    while q:
        x = q.popleft()
        if x == n:
            break
        nd = dist[x] + 1
        for y in g[x]:
            if dist[y] == -1:
                dist[y] = nd
                q.append(y)

    print(dist[n])

if __name__ == "__main__":
    main()

---

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