Overview

This problem asks us to find the shortest path (minimum number of roads traversed) from city \(1\) to city \(N\), using only passable roads.

Analysis

While this is a shortest path problem, the following points are key:

• Shortest path in an unweighted graph: All roads can be considered to have a “length” of \(1\). In such a “graph where all edge weights are equal,” Breadth-First Search (BFS) is the optimal method to find the shortest distance from one vertex to another.
• Handling blocked roads: Roads with \(S_i = 0\) cannot be used for travel. Therefore, by ignoring these roads during graph construction and only adding roads with \(S_i = 1\) to the adjacency list, we can reduce this to a simple shortest path problem.
• Constraints and complexity: Both the number of cities \(N\) and the number of roads \(M\) are on the order of \(2 \times 10^5\). Using BFS, we can solve this in \(O(N + M)\) time complexity, which is well within the time limit.

Algorithm

Approach Using Breadth-First Search (BFS)

1. Graph construction: Create an adjacency list adj using only the road information where \(S_i = 1\).
2. Initialization: Prepare an array dist to hold the shortest distance from city \(1\) to each city, and initialize all elements to \(-1\) (indicating unvisited). Set the distance for the starting city \(1\) as dist[1] = 0.
3. Search:
   • Add city \(1\) to the queue.
   • Repeat the following process until the queue is empty:
     1. Dequeue the current city \(u\) from the front of the queue.
     2. Examine each city \(v\) adjacent to city \(u\) in order.
     3. If city \(v\) is unvisited (dist[v] == -1), update dist[v] = dist[u] + 1 and add city \(v\) to the back of the queue.
4. Output: Output the value of dist[N]. If city \(N\) was never reached and the value remains \(-1\), output \(-1\) as specified in the problem statement.

Complexity

• Time complexity: \(O(N + M)\)
  • Building the adjacency list takes \(O(M)\), and the BFS traversal visits each vertex at most \(1\) time and each edge at most \(2\) times (since edges are bidirectional), resulting in an overall complexity of \(O(N + M)\).
• Space complexity: \(O(N + M)\)
  • The adjacency list requires \(O(N + M)\) memory, and the distance array dist uses \(O(N)\) memory.

Implementation Notes

• Fast I/O: Since \(N, M\) can be large, in Python we use sys.stdin.read().split() to read all input at once, reducing execution time.

• Efficient queue: By using collections.deque, we can perform front element removal (popleft) in \(O(1)\). Since Python’s standard list pop(0) takes \(O(N)\), using deque is recommended in competitive programming.

  Source Code

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

This editorial was generated by gemini-3-flash-thinking.