Overview

This is a problem of finding the minimum number of edges from town \(1\) to town \(N\) on an undirected graph constructed using only passable roads (\(S_i=1\)).
Since the cost of each road is the same (1 per road traversed), the shortest distance can be found using Breadth-First Search (BFS).

Analysis

The essence of this problem is “what is the minimum number of roads to traverse?”
Since every road has the same weight, this directly becomes a shortest path problem (unweighted graph).

Key Observations

• Roads with \(S_i=0\) cannot be used, so they should not be added to the graph in the first place.
• All remaining roads have the same cost (1).
• The shortest distance in an unweighted graph can be found using BFS.

Why a Naive Approach Doesn’t Work

• “Try all possible routes from town 1” using DFS/backtracking is impractical because the number of routes explodes.
• Although the problem states “you may pass through the same town or road any number of times,” unnecessary back-and-forth traversals are not needed when seeking the minimum number of roads.
  The distance at the time BFS first reaches a node is guaranteed to be the minimum.

How to Solve It

• Build an adjacency list using only passable edges.
• Run BFS starting from town 1.
• Maintain dist[v] as “the minimum number of roads from town 1 to town v.”
• Output dist[N] at the end (or -1 if unreachable).

Algorithm

1. Prepare graph as an adjacency list of length N+1 (since town numbers start from 1).
2. Read each road \((u,v,s)\), and only when s==1, perform
   graph[u].append(v), graph[v].append(u) (undirected).
3. Initialize the distance array dist with -1, and set dist[1]=0.
4. Add 1 to the queue and start BFS.
5. Dequeue cur, and for each unvisited adjacent vertex nxt,
   set dist[nxt] = dist[cur] + 1 and add it to the queue.
6. After the search, output dist[N] (it remains -1 if unreachable).

Note: In the provided code, the loop breaks as soon as cur == N is reached.
Since BFS dequeues vertices in non-decreasing order of distance, the shortest distance is already determined at this point, so this is correct.

Complexity

• Time complexity: \(O(N + M)\)
  (Each vertex and each edge is visited at most once)
• Space complexity: \(O(N + M)\)
  (Adjacency list, distance array, queue)

Implementation Notes

• Since the input size can be large, using sys.stdin.readline makes it faster.

• Multiple edges between the same pair of vertices are not a problem. The BFS correctly handles them by checking whether a vertex is unvisited (dist[nxt] == -1).

• Unreachability can be determined directly by checking dist[N] == -1.

  Source Code

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()

This editorial was generated by gpt-5.3-codex.