Overview

This problem asks us to find the shortest path from the starting point (point 1) to the goal point (point \(N\)) in a weighted directed graph.

Analysis

If we consider each point as a “vertex,” each road as an “edge,” and each travel time as an “edge weight,” this reduces to the classic “single-source shortest path problem.”

When solving this problem, we focus on the following points: 1. Edge weights are positive: All road travel times \(C_i\) are at least 1. Under this condition, we can apply “Dijkstra’s algorithm,” which efficiently computes shortest distances. 2. Size of constraints: The number of points \(N\) can be up to \(10^5\) and the number of roads \(M\) can be up to \(2 \times 10^5\), which is relatively large. A naive search (e.g., brute force) would not be fast enough. We need an efficient implementation of Dijkstra’s algorithm using a priority queue (heap).

If we were to use breadth-first search (BFS), it can find shortest paths when all edge weights are the same, but it cannot compute them correctly when weights differ as in this problem. Therefore, Dijkstra’s algorithm, which always finalizes the exploration from the “point that can be reached earliest at the current moment,” is the optimal choice.

Algorithm

Dijkstra’s Algorithm (using a priority queue)

1. Initialization:
   • Prepare an array dist to hold the shortest distance from point 1 to each point, and initialize all values to infinity (\(\infty\)).
   • Set the distance for the starting point as dist[1] = 0.
   • Add (distance 0, point 1) to the priority queue.
2. Exploration:
   • Repeat the following operations until the queue is empty.
   • Extract the “point \(u\) with the smallest distance” from the queue.
   • If the extracted distance is greater than the already recorded dist[u], the data is outdated, so skip it.
   • For each point \(v\) adjacent to point \(u\), compute the new distance via point \(u\): new_dist = dist[u] + (travel time from u to v).
   • If new_dist is smaller than the current dist[v], update dist[v] and add (new_dist, v) to the queue.
3. Termination:
   • The value stored in dist[N] is the shortest travel time from point 1 to point \(N\).

Complexity

• Time complexity: \(O(M \log N)\)
  • Each addition to and extraction from the priority queue takes \(O(\log)\) time, and this is repeated up to \(M\) times, which comfortably fits within the time limit.
• Space complexity: \(O(N + M)\)
  • Storing the graph in adjacency list format requires \(O(N + M)\), and the shortest distance array uses \(O(N)\) memory.

Implementation Notes

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

• Priority queue: Python’s heapq module provides a min-heap, so by storing tuples of (distance, point), we can always extract the point with the minimum distance in \(O(\log (\text{number of elements}))\).

• Early termination: The moment goal point \(N\) is extracted from the queue, its shortest distance is finalized, so we can terminate the search (break) at that point and still obtain the correct answer.

  Source Code

import sys
import heapq

def solve():
    # 標準入力から全てのデータを読み込み、スペースで分割します
    # 大量の入力を処理する場合、sys.stdin.read().split() は高速です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    n = int(next(it))
    m = int(next(it))
    
    # 隣接リストを作成します
    # adj[u] には (終点 v, 移動時間 c) のタプルを格納します
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        c = int(next(it))
        adj[u].append((v, c))
        
    # ダイクストラ法を用いて地点1から各地点への最短時間を求めます
    # dist[i] は地点1から地点iまでの現在の最短時間を保持します
    # 初期値は無限大（float('inf')）に設定します
    dist = [float('inf')] * (n + 1)
    dist[1] = 0
    
    # 優先度付きキュー（ヒープ）には (現在の距離, 地点番号) を格納します
    # Pythonのheapqは最小ヒープなので、距離が小さい順に取り出されます
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # すでに記録されている最短時間より長い場合はスキップします
        if d > dist[u]:
            continue
        
        # ゴールである地点Nに到達した場合、それ以上の探索は不要です（早期終了）
        if u == n:
            break
            
        # 現在の地点 u から移動可能な全ての地点 v について探索します
        for v, weight in adj[u]:
            new_dist = d + weight
            # 地点 v へのより短いルートが見つかった場合、更新してキューに追加します
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
                
    # 地点1から地点Nへの最短時間を出力します
    print(dist[n])

if __name__ == '__main__':
    solve()

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