概要

この問題は、地点1から地点Nまでの最短経路を求めるグラフ上の最短経路問題です。道路ネットワークが与えられ、各道路を通るのに必要な時間が分かっている場合の最小所要時間を求めます。

考察

地点数Nが最大10^5、道路数Mが最大2×10^5と大規模なグラフであるため、単純な深さ優先探索や幅優先探索では効率的に解くことができません。特に、辺の重み（所要時間）が均一でないため、単純なBFSでは正しい解を得られません。

素朴なアプローチとして全経路探索を考えると、経路数が爆発的に増えるため、現実的な時間で計算できません。このような大規模グラフでは、効率的な最短経路アルゴリズムが必要となります。

アルゴリズム

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

アルゴリズムの手順は以下の通りです： 1. 始点（地点1）からの距離を格納する配列を初期化（始点は0、他は無限大） 2. 優先度付きキュー（最小ヒープ）を使用して、未確定の地点の中から最も距離が短い地点を選択 3. 選択した地点から到達可能な隣接地点について、現在の距離より短い経路が見つかれば距離を更新 4. 全ての地点の最短距離が確定するか、目的地点（地点N）の距離が確定するまで繰り返す

ダイクストラ法は貪欲アルゴリズムの一種で、各ステップで最も近い地点を選択することで、効率的に最短経路を求めます。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 各辺は最大1回処理され、ヒープ操作に \(\log N\) の時間がかかるため
• 空間計算量: \(O(N + M)\)
  • グラフの表現に \(O(N + M)\)、距離配列に \(O(N)\)、ヒープに \(O(N)\) のメモリが必要

実装のポイント

• 大規模な入力に対応するため、sys.stdin.read()を使用して高速に入力処理を行う

• グラフを隣接リスト形式で表現し、メモリ効率を向上させる

• 優先度付きキュー（ヒープ）を使用して、次に処理するノードを効率的に選択

• 距離の更新時に、既に確定しているノードをスキップする処理を入れることで効率化

• 到達不能な場合を考慮し、距離が無限大の場合は-1を出力

  ソースコード

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    m = int(data[1])
    
    graph = [[] for _ in range(n+1)]
    index = 2
    for i in range(m):
        a = int(data[index])
        b = int(data[index+1])
        c = int(data[index+2])
        index += 3
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    INF = float('inf')
    dist = [INF] * (n+1)
    dist[1] = 0
    
    heap = [(0, 1)]
    
    while heap:
        current_time, current_node = heapq.heappop(heap)
        
        if current_time > dist[current_node]:
            continue
            
        for neighbor, time in graph[current_node]:
            new_time = current_time + time
            if new_time < dist[neighbor]:
                dist[neighbor] = new_time
                heapq.heappush(heap, (new_time, neighbor))
    
    if dist[n] == INF:
        print(-1)
    else:
        print(dist[n])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。