概要

この問題は、交差点と道路からなるグラフ上で、道路の所要時間と交差点の通行料を考慮した総コストの最小化を求める最短経路問題です。

考察

素朴なアプローチとして、通常のダイクストラ法で各道路の所要時間をコストとして計算すると、交差点の通行料を適切に扱えません。交差点を通過するたびに通行料がかかるため、単純に辺の重みに通行料を加算するだけでは正しいコスト計算ができません。

重要な観察点は、各交差点に入るときに一度だけ通行料が発生することです。つまり、交差点vに初めて到達した時点で、その交差点の通行料\(C_v\)を支払う必要があります。この性質から、ダイクストラ法のコスト計算において、現在の交差点から次の交差点に移動する際に、移動コスト（道路の所要時間）に加えて、次の交差点の通行料を加算することで正しく処理できます。

アルゴリズム

以下の手順でダイクストラ法を適用します：

1. グラフを隣接リストで表現する
2. 各交差点の通行料を配列tollsに記録する（有料エリアがない交差点は0）
3. 距離配列distを初期化し、始点（交差点1）のコストをtolls[1]（出発地点の通行料）に設定
4. 優先度付きキューを使用し、現在の交差点から次の交差点への移動コストを計算：
   • 新しいコスト = 現在のコスト + 道路の所要時間 + 次の交差点の通行料
5. この新しいコストが現在の最小コストより小さい場合に更新する
6. 終点（交差点N）に到達した時点で最小コストが求まる

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法の標準的な計算量。各ノードと辺を最大1回処理し、優先度付きキュー操作に\(\log N\)かかる
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストと距離配列のメモリ使用量

実装のポイント

• 有料エリアがない交差点の通行料は0になるよう、配列を初期化する

• 大きな数値（\(10^{18}\)）を無限大として使用し、オーバーフローを防ぐ

• 優先度付きキューの効率的な使用のために、コストが現在の最小値と一致しない場合はスキップする

• 終点に到達した時点で早期終了することで、無駄な計算を省く

  ソースコード

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    n = int(next(it)); m = int(next(it)); k = int(next(it))
    
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    tolls = [0] * (n+1)
    for _ in range(k):
        l = int(next(it)); c = int(next(it))
        tolls[l] = c
    
    INF = 10**18
    dist = [INF] * (n+1)
    dist[1] = tolls[1]
    
    heap = [(dist[1], 1)]
    
    while heap:
        d, node = heapq.heappop(heap)
        if d != dist[node]:
            continue
        if node == n:
            break
            
        for neighbor, weight in graph[node]:
            new_cost = d + weight + tolls[neighbor]
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(heap, (new_cost, neighbor))
                
    print(dist[n])

if __name__ == "__main__":
    main()

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