概要

この問題は、重み付き無向グラフにおいて、頂点 \(1\) から頂点 \(N\) までの最短距離を求める問題です。到達できない場合は \(-1\) を出力します。

考察

この問題は典型的な「最短経路探索」の問題であり、グラフ上の各辺には移動にかかる時間が設定されています。このようなケースでは、全探索（例えば深さ優先探索）では計算量が非常に大きくなり、現実的ではありません。

素朴な方法として、幅優先探索（BFS）が考えられますが、これはすべての辺の重みが等しい場合に有効です。しかし、今回は各辺に異なる重み（時間）があるため、単純なBFSでは最短時間を求めることはできません。

そこで、ダイクストラ法（Dijkstra’s Algorithm）というアルゴリズムが適しています。ダイクストラ法は、非負の重みを持つグラフにおける単一始点最短経路を効率的に求めることができます。

また、到達不能なケースに対応するため、最終的に頂点 \(N\) の最短距離が更新されていない（初期値のまま）かどうかを確認する必要があります。

アルゴリズム

ダイクストラ法を用います。以下のような手順で実行します：

1. 各頂点への最短距離を管理する配列 dist を用意し、初期値は無限大（float('inf')）とします。ただし、スタート地点（頂点 \(1\)）の距離は \(0\) とします。
2. 優先度付きキュー（ヒープ）を用いて、現在いる頂点とそこまでの最短距離を管理します。
3. キューから最も距離が小さい頂点を取り出し、それに隣接する頂点に対して、より短い経路が見つかれば dist を更新し、キューに追加します。
4. 頂点 \(N\) に到達した時点で、その時点での距離が答えとなります。
5. 全ての探索が終了しても頂点 \(N\) に到達できなかった場合は -1 を出力します。

計算量

• 時間計算量: \(O(M \log N)\)
  　→ 各辺を最大1回処理し、優先度付きキューへの挿入・取り出しに \(\log N\) かかります。
• 空間計算量: \(O(N + M)\)
  　→ グラフの隣接リスト表現に \(O(N + M)\) 必要です。

実装のポイント

• 頂点番号は \(1\) から始まっているので、内部的には \(0\) から \(N-1\) に変換して扱うと便利です。
• ヒープには (距離, 頂点) のタプルを入れ、距離の小さい順に取り出すようにします。
• 更新済みの頂点を再度処理しないために、dist[u] < d の場合はスキップする処理が必要です。
• 最短経路が見つかった時点で即座に答えを出力することで、若干の高速化が可能です。

## ソースコード

```python
import heapq
import sys

def main():
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N)]
    
    for _ in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        a -= 1
        b -= 1
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    dist = [float('inf')] * N
    dist[0] = 0
    pq = [(0, 0)]  # (distance, node)
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == N - 1:
            print(d)
            return
        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(-1)

if __name__ == "__main__":
    main()

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