概要

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

考察

地点の数が最大 \(10^5\)、道路の数が最大 \(2 \times 10^5\) と非常に大きいため、全ての経路を探索するような素朴な方法では間に合いません。また、各道路の所要時間（コスト）が \(1\) とは限らないため、単純な幅優先探索（BFS）では最短距離を求めることができません。

負の重みを持つ道路は存在しないため、このような「単一始点最短経路問題」を効率よく解くにはダイクストラ法を用いるのが最適です。

アルゴリズム

ダイクストラ法

ダイクストラ法は、未確定の地点の中で「始点からの距離が最も近い地点」から順に探索を確定させていく手法です。効率的に「最小の距離」を取り出すために、優先度付きキュー（ヒープ）を利用します。

1. 初期化: 始点（地点 \(1\)）の距離を \(0\)、それ以外の地点の距離を無限大（\(\infty\)）に設定します。
2. 探索:
   • 優先度付きキューから、現在の最短距離を持つ地点 \(u\) を取り出します。
   • もし取り出した距離が、すでに記録されている最短距離より大きければ、そのデータは古いので無視します。
   • 地点 \(u\) に隣接する各地点 \(v\) について、地点 \(u\) を経由するルート（dist[u] + 道路の重み）が現在の dist[v] より短ければ、dist[v] を更新し、優先度付きキューに (新しい距離, v) を追加します。
3. 終了: 地点 \(N\) に到達するか、キューが空になるまで繰り返します。

最終的に dist[N] が無限大のままであれば到達不可能と判断し、そうでなければその値を出力します。

計算量

• 時間計算量: \(O(M \log N)\)
  • 各道路を最大1回ずつ調べ、優先度付きキューへの追加・取り出し操作（\(\log N\)）が発生するため、制約内で十分に高速に動作します。
• 空間計算量: \(O(N + M)\)
  • 隣接リストによるグラフの保持と、各地点の距離を格納する配列が必要です。

実装のポイント

• 高速な入出力: 地点数や道路数が多いため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 双方向の道路: 問題文に「双方向に結んでいる」とあるため、隣接リストを作成する際は \(A_i\) から \(B_i\) だけでなく、\(B_i\) から \(A_i\) へのエッジも追加する必要があります。

• 枝刈り: 優先度付きキューから取り出した距離 d が、現在の dist[u] よりも大きい場合（if d > dist[u]: continue）は、すでに他のより短いルートで更新済みであることを意味します。この確認を入れることで、無駄な探索を省くことができます。

  ソースコード

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

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