概要

重み（所要時間）付き無向グラフで、地点 \(1\) から地点 \(N\) までの最短距離（最小合計時間）を求める問題です。到達できない場合は -1 を出力します。

考察

各地点を頂点、道路を辺、所要時間 \(C_i\) を辺の重みとみなすと、「始点 \(1\) から終点 \(N\) への最短路問題」になります。

• 重要な気づき: 所要時間 \(C_i\) はすべて \(1\) 以上（正の重み）なので、最短路は ダイクストラ法で効率よく求められます。
• 素朴な方法がダメな理由
  • 全経路を探索する（DFSで全パス列挙など）のは経路数が爆発し不可能です。
  • BFSは「辺の重みがすべて同じ」場合のみ最短路を保証します。今回は \(C_i\) がさまざまなので不適切です。
  • ベルマンフォード法は \(O(NM)\) で、最大で \(10^5 \times 2\times 10^5\) となり現実的ではありません。
• 解決策: 優先度付きキュー（ヒープ）を用いたダイクストラ法で、常に「現時点で最短と確定できる候補」から距離更新していけば高速に解けます。

（例）
\(1 \to 2\) が 100 分、\(1 \to 3\) が 1 分、\(3 \to 2\) が 1 分のとき、BFSだと「辺数が少ない」\(1\to2\) を先に選びがちですが、最短時間は \(1\to3\to2\) の 2 分です。重みがあるのでダイクストラ法が必要です。

アルゴリズム

ダイクストラ法（正の重みの最短路）を用います。

1. 隣接リストでグラフを作る（無向なので両方向に追加）。
2. 距離配列 dist を用意し、dist[1]=0、それ以外は十分大きい値（INF）。
3. 優先度付きキューに (距離, 頂点) を入れて開始する。
4. キューから最小距離の要素 (d, v) を取り出す。
   • もし d != dist[v] なら、それは古い情報（より短い更新が既に入っている）なので無視する。
5. 頂点 v から出る各辺 (v -> to, 重み w) について、
   • nd = d + w が dist[to] より小さければ更新し、キューに (nd, to) を追加する。
6. dist[N] が INF のままなら到達不能なので -1、そうでなければ dist[N] を出力する。
   • コードでは v == N を取り出した時点で打ち切ることで少し高速化しています（ダイクストラ法では取り出した時点の距離が確定するため）。

計算量

• 時間計算量: \(O\big((N+M)\log N\big)\)
  （各辺の緩和が高々数回、ヒープ操作が \(\log N\)）
• 空間計算量: \(O(N+M)\)
  （隣接リストと距離配列、ヒープ）

実装のポイント

• 入力が大きいので sys.stdin.buffer.read() でまとめ読みし高速化しています。

• 無向グラフなので g[a].append((b,c)) と g[b].append((a,c)) の両方を追加します。

• ヒープから取り出した (d, v) が古い可能性があるため、if d != dist[v]: continue で捨てるのが定石です。

• 距離の最大は \(10^9\) の辺が多数足されうるので、INF は 10**30 のように十分大きく取ります。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        a = next(it); b = next(it); c = next(it)
        g[a].append((b, c))
        g[b].append((a, c))

    INF = 10**30
    dist = [INF] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]

    while pq:
        d, v = heapq.heappop(pq)
        if d != dist[v]:
            continue
        if v == N:
            break
        for to, w in g[v]:
            nd = d + w
            if nd < dist[to]:
                dist[to] = nd
                heapq.heappush(pq, (nd, to))

    ans = dist[N]
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。