概要

重み（所要時間）付きの有向グラフで、地点 \(1\) から地点 \(N\) までの最短到達時間を求める問題です。辺の重みがすべて正なので、ダイクストラ法で解けます。

考察

各地点を頂点、道路を「\(U \rightarrow V\) にコスト \(C\)」の有向辺とみなすと、この問題は「始点 \(1\) から終点 \(N\) への最短路問題」そのものです。

素朴に「全ての経路を列挙して最短を取る」ことは、分岐があるたびに経路数が爆発し現実的ではありません。また、BFS（幅優先探索）は「辺の本数が最短（コストは無視）」の最短路は求められますが、今回はコスト \(C_i\) が \(1\) とは限らないため正しい答えになりません（例：1本でコスト100の道と、2本でコスト1+1の道があるとき、BFSは1本の方を選んでしまう）。

ここで重要な観察は次の通りです。

• すべてのコストが正（\(C_i \ge 1\)）
  → 「確定した最短距離は後から更新されない」という性質が成り立つ
  → 優先度付きキューを使うダイクストラ法が適用でき、\(N=10^5, M=2\times10^5\) でも高速に解ける

アルゴリズム

ダイクストラ法を用いて、各地点への最短時間 dist を求めます。

1. 隣接リスト g[u] = [(v, c), ...] を作る（有向辺なので片方向のみ追加）。
2. dist[1] = 0、それ以外は十分大きい値（INF）で初期化。
3. 優先度付きキュー（最小ヒープ）に (0, 1) を入れる。
4. キューから「現時点で最短距離が最小の頂点」 (d, u) を取り出す。
   • もし d != dist[u] なら、古い情報（後でより短い距離で更新された）なので無視する。
5. u から出る各辺 (u -> v, w) について、nd = d + w を計算し、
   • nd < dist[v] なら dist[v] = nd に更新して、キューに (nd, v) を入れる。
6. これを繰り返すと、最終的に dist[N] が最短時間になる。
   • コードでは u == N になった時点で打ち切り（その時点で dist[N] は確定）して少し高速化しています。

簡単な例： - \(1 \to 2\)（5）, \(1 \to 3\)（2）, \(3 \to 2\)（1）
最短は \(1 \to 3 \to 2\) で \(2+1=3\)。
ダイクストラ法は「まず距離2の頂点3を確定→そこから2を距離3に更新」という流れで正しく求めます。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （各辺の緩和が最大1回の更新を引き起こし、ヒープ操作が \(\log N\)）
• 空間計算量: \(O(N+M)\)
  （隣接リストと距離配列、ヒープ）

実装のポイント

• 隣接リストで持つ（\(M\) が大きいので隣接行列は不可）。

• INF は最大距離より十分大きくする（ここでは 10**30）。
  コスト最大は \(10^9\)、経路長は最大でも \(N-1\) 辺程度なので \(10^{14}\) 規模になり得ます。

• ヒープから取り出した (d, u) が 最新の dist[u] と一致しない場合は捨てる（if d != dist[u]: continue）。これがないと同じ頂点が何度も処理されて遅くなります。

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

  ソースコード

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):
        u = next(it); v = next(it); c = next(it)
        g[u].append((v, c))

    INF = 10**30
    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 g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    print(dist[N])

if __name__ == "__main__":
    main()

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