概要

交差点に通行料が設定されたグラフ上で、交差点 \(1\) から交差点 \(N\) までの最短コスト経路を求める問題です。コストは「移動時間」と「通過した交差点の通行料」の合計です。

考察

この問題は、単純な最短経路探索ではなく、ノード（交差点）に重みがあるという点が特徴です。通常のダイクストラ法では辺の重みだけを考えますが、今回は各ノードにもコスト（通行料）が存在します。

重要な観察

• 各ノードの通行料は、そのノードに到達した時点で支払う必要がある。
• 出発地（交差点 \(1\)）および目的地（交差点 \(N\)）の通行料も含まれるため、初期コストとして toll[1] を設定する必要がある。
• 単純に辺の重みだけを考慮するのではなく、「現在のノードまでのコスト + 辺の重み + 次のノードの通行料」を次のコストとして扱う必要があります。

素朴なアプローチの問題点

例えば、すべての辺の重みに隣接ノードの通行料を加える方法を思いつくかもしれませんが、これは無駄が多く、また正確ではありません（同じノードに複数回訪れる場合に多重カウントしてしまう可能性がある）。

解決方法

ダイクストラ法を拡張して、ノードのコストを含めた状態で最短距離を管理するのが適切です。具体的には： - 頂点 \(u\) までの最小コストを dist[u] に保持。 - ノード \(u\) から隣接ノード \(v\) に移動する際の新しいコストは
$\( \text{dist}[u] + \text{edge\_weight}(u, v) + \text{toll}[v] \)$
となり、これをヒープで管理しながら探索します。

アルゴリズム

この問題は ダイクストラ法 を用いることで効率的に解けます。

手順

1. グラフを隣接リスト形式で構築します。
2. 各交差点の通行料を配列 toll に格納します。
3. ダイクストラ法を実行します：
   • 初期状態では dist[1] = toll[1]（出発地の通行料を含む）
   • ヒープには (コスト, ノード) の形で要素を入れる
   • 各ノードから遷移する際に、次ノードの通行料を加味してコストを更新
4. ノード \(N\) に到達した時点でそのコストを出力すればよい。

計算量

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

ダイクストラ法における優先度付きキュー（ヒープ）の操作が最大 \(N + M\) 回行われ、各操作が \(\log N\) なので、全体で上記の計算量になります。

実装のポイント

• ヒープから取り出したコストがすでに更新済みのものであればスキップする（典型処理）
• 通行料は各ノードに紐づいているので、辺の重みとは別に管理する
• 初期コストに toll[1] を忘れずに含める
• グラフは無向グラフなので、両方向に辺を追加することに注意

## ソースコード

```python
import heapq
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    # グラフ構築
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 通行料情報
    toll = [0] * (N+1)
    for _ in range(K):
        l = int(data[idx]); idx += 1
        c = int(data[idx]); idx += 1
        toll[l] = c
    
    # ダイクストラ法
    dist = [float('inf')] * (N+1)
    dist[1] = toll[1]
    pq = [(toll[1], 1)]  # (cost, node)
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == N:
            print(d)
            return
        for v, w in graph[u]:
            new_cost = d + w + toll[v]
            if new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(pq, (new_cost, v))

if __name__ == "__main__":
    main()

---

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