概要

この問題は、道路の所要時間（辺の重み）と交差点の通行料（頂点の重み）の両方を考慮した、地点 \(1\) から地点 \(N\) までの最短経路（最小コスト）を求める問題です。

考察

最短経路を求めるアルゴリズムとして有名な「ダイクストラ法」は、通常、辺の重み（道路の所要時間）のみを扱います。しかし、この問題では頂点（交差点）を通過する際にもコストが発生します。

ここで重要なのは、「ある交差点 \(u\) から隣の交差点 \(v\) へ移動する」という一連の動作にかかるコストを、(道路の所要時間 \(W\)) + (移動先の交差点 \(v\) の通行料 \(C_v\)) とみなすことです。

ただし、この考え方だけでは「出発地点（交差点 \(1\)）の通行料」が計算から漏れてしまいます。問題文には「出発地点と到着地点に有料エリアがある場合も加算される」とあるため、初期状態として「交差点 \(1\) に到達した時点でのコスト」を「交差点 \(1\) の通行料」として設定することで、正しく計算できるようになります。

すべての辺の重み（道路の所要時間）と頂点の重み（通行料）が正であるため、ダイクストラ法を適用して効率的に解くことが可能です。

アルゴリズム

重み付きグラフの単一始点最短経路問題を解くための「ダイクストラ法」を使用します。

1. 準備:
   • 各交差点への最小コストを保持する配列 dist を無限大（\(10^{18}\) など）で初期化します。
   • dist[1] を「交差点 \(1\) の通行料」に設定します。
   • 優先度付きキュー（ヒープ）を用意し、(dist[1], 1) を追加します。
2. 探索:
   • キューから最小コスト \(d\) を持つ交差点 \(u\) を取り出します。
   • すでに d > dist[u] であれば、その情報は古いので無視します。
   • 交差点 \(u\) に隣接する各交差点 \(v\) （道路の重みを \(w\) とする）に対して、以下の計算を行います。
     • 新しいコスト = d + w + (交差点 v の通行料)
     • 新しいコスト < dist[v] であれば、dist[v] を更新し、キューに (新しいコスト, v) を追加します。
3. 終了:
   • 交差点 \(N\) に到達した際、あるいはキューが空になった際の dist[N] が答えとなります。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • 優先度付きキューを用いたダイクストラ法の計算量です。各辺を最大 \(1\) 回ずつ調べ、キューの挿入・取り出し操作に \(O(\log N)\) かかります。
• 空間計算量: \(O(N + M)\)
  • 隣接リスト形式のグラフ、各頂点のコスト、通行料を保持する配列が必要です。

実装のポイント

• 通行料の保持: 全ての交差点に有料エリアがあるわけではないため、デフォルト値を \(0\) とした配列 tolls を作成し、与えられた \(K\) 箇所の情報を上書きするのが効率的です。

• 大きな値の扱い: \(N, M\) が最大 \(2 \times 10^5\) で、各コストが最大 \(10^9\) であるため、総コストは \(10^{14}\) を超える可能性があります。プログラム内で無限大として扱う値は十分に大きく設定する必要があります。

• 入出力の高速化: \(N, M\) が大きいため、Python の場合は sys.stdin.read().split() などを用いて一括で入力を読み込むと実行速度が向上します。

  ソースコード

import heapq
import sys

def solve():
    # 入力を一度にすべて読み込み、スペースや改行で分割してトークンのリストを作成します
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not input_data:
        return
    
    # イテレータを使用してトークンを1つずつ処理します（メモリ効率と速度のため）
    tokens = map(int, input_data)
    
    # 交差点の数 N、道路の数 M、有料エリアの数 K を取得
    try:
        N = next(tokens)
        M = next(tokens)
        K = next(tokens)
    except StopIteration:
        return
    
    # 隣接リストを作成してグラフを表現します
    # 各交差点（1-indexed）に対して、(接続先, 所要時間) のリストを保持します
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        try:
            u = next(tokens)
            v = next(tokens)
            w = next(tokens)
            # 道路は双方向に通行可能です
            adj[u].append((v, w))
            adj[v].append((u, w))
        except StopIteration:
            break
            
    # 各交差点の通行料を格納する配列を作成します
    tolls = [0] * (N + 1)
    for _ in range(K):
        try:
            l = next(tokens)
            c = next(tokens)
            tolls[l] = c
        except StopIteration:
            break
            
    # ダイクストラ法を用いて最小コストを求めます
    # dist[i] は交差点 1 から交差点 i までの最小コストを保持します
    inf = 10**18
    dist = [inf] * (N + 1)
    
    # 出発地点（交差点 1）の通行料を初期コストとして設定します
    dist[1] = tolls[1]
    
    # 優先度付きキュー（ヒープ）には (現在の総コスト, 現在の交差点) を格納します
    pq = [(dist[1], 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # すでに確定している最小コストより大きい場合はスキップします
        if d > dist[u]:
            continue
        
        # 目的地である交差点 N に到達した場合、最初に取り出されたときが最小コストです
        if u == N:
            break
        
        # 隣接するすべての交差点を探索します
        for v, w in adj[u]:
            # 新しい地点 v への移動コスト = 現在までのコスト + 道路の所要時間 + 到着した交差点の通行料
            new_cost = d + w + tolls[v]
            
            # これまでに見つかったコストより小さい場合、情報を更新してキューに追加します
            if new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(pq, (new_cost, v))
                
    # 交差点 1 から 交差点 N までの最小コストを出力します
    print(dist[N])

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。