Overview

This problem asks us to find the shortest path (minimum cost) from point \(1\) to point \(N\) in a weighted undirected graph.

Analysis

Since the number of points can be up to \(10^5\) and the number of roads can be up to \(2 \times 10^5\), which are very large, a naive approach that explores all possible paths will not run in time. Additionally, since the travel time (cost) of each road is not necessarily \(1\), a simple breadth-first search (BFS) cannot find the shortest distance.

Since there are no roads with negative weights, Dijkstra’s algorithm is the optimal choice for efficiently solving this type of “single-source shortest path problem.”

Algorithm

Dijkstra’s Algorithm

Dijkstra’s algorithm works by progressively finalizing the exploration starting from the “point with the smallest distance from the source” among all unfinalized points. A priority queue (heap) is used to efficiently extract the “minimum distance.”

1. Initialization: Set the distance of the source (point \(1\)) to \(0\), and the distance of all other points to infinity (\(\infty\)).
2. Exploration:
   • Extract the point \(u\) with the current shortest distance from the priority queue.
   • If the extracted distance is greater than the already recorded shortest distance, this data is outdated, so ignore it.
   • For each point \(v\) adjacent to point \(u\), if the route through point \(u\) (dist[u] + road weight) is shorter than the current dist[v], update dist[v] and add (new distance, v) to the priority queue.
3. Termination: Repeat until point \(N\) is reached or the queue becomes empty.

Finally, if dist[N] remains infinity, we determine that the destination is unreachable; otherwise, we output that value.

Complexity

• Time complexity: \(O(M \log N)\)
  • Each road is examined at most once, and each addition/extraction operation on the priority queue costs \(\log N\), so this runs sufficiently fast within the constraints.
• Space complexity: \(O(N + M)\)
  • We need an adjacency list to store the graph and an array to store the distance to each point.

Implementation Notes

• Fast I/O: Since the number of points and roads can be large, in Python, reading all input at once using sys.stdin.read().split() can reduce execution time.

• Bidirectional roads: Since the problem states that roads “connect bidirectionally,” when constructing the adjacency list, we need to add not only an edge from \(A_i\) to \(B_i\) but also an edge from \(B_i\) to \(A_i\).

• Pruning: If the distance d extracted from the priority queue is greater than the current dist[u] (if d > dist[u]: continue), it means the point has already been updated via another shorter route. Including this check eliminates unnecessary exploration.

  Source Code

import heapq
import sys

def solve():
    # 入力を一括で読み込み、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 隣接リストの作成
    adj = [[] for _ in range(N + 1)]
    for i in range(M):
        u = int(input_data[2 + 3*i])
        v = int(input_data[3 + 3*i])
        w = int(input_data[4 + 3*i])
        adj[u].append((v, w))
        adj[v].append((u, w))
        
    # ダイクストラ法のための初期化
    # dist[i] は地点1から地点iまでの最小所要時間
    inf = float('inf')
    dist = [inf] * (N + 1)
    dist[1] = 0
    
    # 優先度付きキュー (現在の最短距離, 地点番号)
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # すでにより短い経路が見つかっている場合はスキップ
        if d > dist[u]:
            continue
        
        # ゴール地点に到達した場合は早期終了可能
        if u == N:
            break
            
        # 隣接する地点を探索
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
                
    # 地点Nまでの距離が無限大のままなら到達不可
    if dist[N] == inf:
        print("-1")
    else:
        print(dist[N])

if __name__ == "__main__":
    solve()

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