概要

この問題は、重み付き有向グラフにおいて、スタート地点（地点1）からゴール地点（地点 \(N\)）までの最短経路を求める問題です。

考察

各地点を「頂点」、道路を「辺」、移動時間を「辺の重み」と考えると、典型的な「単一始点最短経路問題」に帰着できます。

この問題を解くにあたって、以下の点に注目します： 1. 辺の重みが正である: すべての道路の移動時間 \(C_i\) は 1 以上です。この条件がある場合、効率的に最短距離を求められる「ダイクストラ法」が適用できます。 2. 制約の大きさ: 地点の数 \(N\) が最大 \(10^5\)、道路の数 \(M\) が最大 \(2 \times 10^5\) と比較的大きいため、単純な探索（全探索など）では間に合いません。優先度付きキュー（ヒープ）を用いた高速なダイクストラ法が必要です。

もし幅優先探索（BFS）を用いると、すべての辺の重みが同じ場合には最短経路を求められますが、今回のように重みが異なる場合には正しく計算できません。そのため、常に「現時点で最も早く到達できる地点」から順に探索を確定させていくダイクストラ法が最適です。

アルゴリズム

ダイクストラ法（優先度付きキュー利用）

1. 初期化:
   • 地点 1 から各地点への最短距離を保持する配列 dist を用意し、すべて無限大（\(\infty\)）で初期化します。
   • スタート地点の距離 dist[1] = 0 とします。
   • 優先度付きキューに (距離 0, 地点 1) を追加します。
2. 探索:
   • キューが空になるまで、以下の操作を繰り返します。
   • キューから「最も距離が小さい地点 \(u\)」を取り出します。
   • もし取り出した距離が、既に記録されている dist[u] より大きければ、そのデータは古いので無視します。
   • 地点 \(u\) から隣接する各地点 \(v\) について、地点 \(u\) を経由した新しい距離 new_dist = dist[u] + (uからvへの時間) を計算します。
   • new_dist が現在の dist[v] よりも小さければ、dist[v] を更新し、キューに (new_dist, v) を追加します。
3. 終了:
   • dist[N] に格納されている値が、地点 1 から地点 \(N\) への最短時間となります。

計算量

• 時間計算量: \(O(M \log N)\)
  • 優先度付きキューへの追加・取り出しに \(\log\) の時間がかかり、それを辺の数 \(M\) の回数分繰り返すため、制限時間内に十分間に合います。
• 空間計算量: \(O(N + M)\)
  • 隣接リスト形式でグラフを保持するのに \(O(N + M)\)、最短距離の配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, M\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 優先度付きキュー: Python の heapq モジュールは最小ヒープを提供しているため、(距離, 地点) のタプルを格納することで、常に最小距離の地点を \(O(\log (\text{要素数}))\) で取り出すことができます。

• 早期終了: ゴール地点 \(N\) がキューから取り出された瞬間、その地点への最短距離は確定しているため、そこで探索を終了（break）しても正解を得ることができます。

  ソースコード

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

---

この解説は gemini-3-flash-preview によって生成されました。