概要

この問題は、重み付き有向グラフにおいて、頂点 \(1\) から頂点 \(N\) までの最短距離を求める問題です。

考察

この問題は典型的な「単一始点最短経路問題」であり、ダイクストラ法（Dijkstra’s algorithm）を用いることで効率的に解くことができます。

素朴な方法として、全探索や幅優先探索（BFS）などがありますが、辺の重みがあるため単純なBFSでは最短距離が求められません。また、辺の数が最大で \(2 \times 10^5\) あるため、計算量の大きいアルゴリズム（例えばワーシャル–フロイド法 \(O(N^3)\)）を使うと時間制限に間に合いません。

そこで、辺の重みが非負であるという性質を利用して、ダイクストラ法を適用します。ダイクストラ法は優先度付きキュー（ヒープ）を使うことで、効率的に最小コストの頂点を選択しながら最短距離を更新していきます。

アルゴリズム

1. グラフを隣接リスト形式で表現する。
2. 各頂点までの最短距離を管理する配列 dist を用意し、初期値は無限大（\(\infty\)）とする。ただし、始点（頂点 \(1\)）の距離は \(0\) とする。
3. 優先度付きキュー（ヒープ）に (距離, 頂点) の形で始点を追加する。
4. キューが空になるまで以下を繰り返す：
   • キューから最も距離が小さい頂点を取り出す。
   • その頂点から伸びる各辺に対して、新しい経路がより短ければ dist を更新し、キューに追加する。
5. 最終的に dist[N] に頂点 \(1\) から \(N\) までの最短距離が格納されている。

例

例えば、以下のような入力があったとします：

4 5
1 2 2
1 3 5
2 3 1
2 4 7
3 4 3

このとき、頂点 \(1\) から \(4\) への最短経路は \(1 \to 2 \to 3 \to 4\) で、距離は \(2 + 1 + 3 = 6\) となります。

計算量

• 時間計算量: \(O((N + M) \log N)\)
• 空間計算量: \(O(N + M)\)

ここで、\(N\) は頂点数、\(M\) は辺数です。優先度付きキューの操作に \(\log N\) が掛かるため、全体で上記の計算量になります。

実装のポイント

• グラフは隣接リストで持つと効率的。
• 距離の初期化は float('inf') で行う。
• 優先度付きキューには (距離, 頂点) のタプルを入れることで、距離の小さい順に取り出せる。
• 同じ頂点でも複数回キューに入ることがあるため、取り出したときに既に最短距離が更新されていないかチェックする必要がある。

## ソースコード

```python
import heapq
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    graph = [[] for _ in range(N + 1)]
    
    index = 2
    for _ in range(M):
        u = int(data[index])
        v = int(data[index + 1])
        c = int(data[index + 2])
        graph[u].append((v, c))
        index += 3
    
    # Dijkstra's algorithm
    dist = [float('inf')] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]  # (distance, node)
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
            
        for v, cost in graph[u]:
            new_dist = dist[u] + cost
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    
    print(dist[N])

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。