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 (\(S_i = 1\)). This is a classic shortest path problem on an unweighted graph and can be solved using BFS (Breadth-First Search).

Analysis

Key Observations

• The “length” of each road is all \(1\) (unweighted graph).
• Roads that are closed (\(S_i = 0\)) cannot be used at all, so we simply don’t include them in the graph from the start.
• The problem reduces to finding the shortest distance from city \(1\) to city \(N\) on a graph composed only of passable roads.

Why BFS?

• For weighted graphs, algorithms like Dijkstra’s would be needed, but in this problem all edge weights are \(1\) (uniform).
• The shortest path on a graph with uniform weights can be found with BFS in \(O(N + M)\).
• For example, DFS (Depth-First Search) does not guarantee the shortest path, so BFS must be used.

Concrete Example

Consider the case with 4 cities and the following roads:

• Road 1: City \(1\) ↔ City \(2\) (passable)
• Road 2: City \(2\) ↔ City \(4\) (closed)
• Road 3: City \(1\) ↔ City \(3\) (passable)
• Road 4: City \(3\) ↔ City \(4\) (passable)

Using only passable roads, the path \(1 \to 3 \to 4\) with \(2\) roads is the shortest. Since there is no way to reach city \(4\) from city \(2\) (road 2 is closed), we must take this detour.

Algorithm

1. Graph Construction: Read the input and add only roads with \(S_i = 1\) (passable) to the adjacency list.
2. BFS Execution: Perform BFS starting from city \(1\) to find the shortest distance to each city.
   • Use a queue (FIFO) to explore cities in order of increasing distance from the starting point.
   • Since the first time a city is visited gives its shortest distance, we do not revisit cities that have already been visited.
3. Output the Result: Output the shortest distance to city \(N\). If city \(N\) is unreachable, output \(-1\).

Visualization of BFS operation:

Distance 0: Enqueue city 1
Distance 1: Enqueue adjacent vertices of city 1
Distance 2: Enqueue adjacent vertices of the vertices at distance 1
...(continue until city N is reached)

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) for graph construction, \(O(N + M)\) for BFS (each vertex and each edge is processed at most once)
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) for the adjacency list, \(O(N)\) for the distance array and queue

Implementation Notes

• Filtering closed roads: By adding only roads with \(S_i = 1\) during graph construction, there is no need for conditional branching during BFS.

• Early termination: The implementation outputs the answer and terminates immediately when city \(N\) is reached during BFS. Since BFS guarantees that the distance at the first time of arrival is the shortest, this produces the correct result.

• Using deque: In Python, using collections.deque allows \(O(1)\) removal from the front of the queue (popleft()). Since pop(0) on a list costs \(O(N)\), always use deque.

  Source Code

from collections import deque

def main():
    import sys
    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)
    
    # BFS from 1 to N
    dist = [-1] * (N + 1)
    dist[1] = 0
    queue = deque([1])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if dist[nxt] == -1:
                dist[nxt] = dist[node] + 1
                if nxt == N:
                    print(dist[N])
                    return
                queue.append(nxt)
    
    print(dist[N])

main()

---

This editorial was generated by claude4.6opus-thinking.