概要

交差点にかかる通行料を考慮しつつ、交差点 \(1\) から交差点 \(N\) への最短コスト（道路の所要時間＋通行料の合計）を求める、重み付き最短経路問題です。

考察

問題の本質を見抜く

この問題では、移動のコストが2種類あります：

1. 道路の所要時間（辺の重み）
2. 交差点の通行料（頂点の重み）

通常のダイクストラ法は「辺の重み」だけを扱いますが、この問題では「頂点の重み」も加わります。

頂点コストを辺コストに統合する

重要な気づきは、頂点にかかるコスト（通行料）を、辺の移動コストに組み込むことでダイクストラ法がそのまま使えるという点です。

具体的には、ある交差点 \(u\) から道路（所要時間 \(w\)）を通って交差点 \(v\) に到着するとき、そのコストを次のように考えます：

\[\text{遷移コスト} = w + \text{toll}[v]\]

つまり「道路の所要時間＋到着先の通行料」を辺のコストとみなします。出発地点（交差点 \(1\)）の通行料は初期コストとして最初に加算しておきます。

具体例

例えば、交差点が3つで： - 道路：\(1 \to 2\)（所要時間 \(5\)）、\(2 \to 3\)（所要時間 \(3\)） - 通行料：交差点 \(2\) に通行料 \(10\)

の場合、\(1 \to 2 \to 3\) の総コストは \(\text{toll}[1] + 5 + \text{toll}[2] + 3 + \text{toll}[3] = 0 + 5 + 10 + 3 + 0 = 18\) となります。

これはダイクストラの遷移で、\(\text{dist}[1] = \text{toll}[1] = 0\) から始めて、\(\text{dist}[2] = 0 + 5 + 10 = 15\)、\(\text{dist}[3] = 15 + 3 + 0 = 18\) と正しく計算されます。

アルゴリズム

1. 各交差点の通行料を配列 \(\text{toll}\) に格納する（有料エリアがない交差点は \(0\)）。
2. ダイクストラ法を実行する：
   • 初期状態：\(\text{dist}[1] = \text{toll}[1]\)（出発地の通行料）
   • 遷移：交差点 \(u\) から辺（重み \(w\)）で交差点 \(v\) に行くとき、\(\text{dist}[v] = \text{dist}[u] + w + \text{toll}[v]\) で更新
3. \(\text{dist}[N]\) が答え。

これにより、通過した全交差点の通行料と全道路の所要時間の合計が最小となる経路のコストが求まります。

計算量

• 時間計算量: \(O((N + M) \log N)\)（ダイクストラ法の標準的な計算量）
• 空間計算量: \(O(N + M)\)（隣接リストと距離配列）

実装のポイント

• 高速入力: \(N, M\) が最大 \(2 \times 10^5\) のため、sys.stdin.buffer.read() でまとめて読み込むことで入出力を高速化しています。

• 早期終了: ダイクストラ法でノード \(N\) を初めてヒープから取り出した時点で最短距離が確定するため、if u == N: break で打ち切っています。

• 頂点コストの統合: 到着先ノードの通行料を辺のコストに加算する形にすることで、特別な処理なく標準的なダイクストラ法の枠組みで解けます。出発地点の通行料だけは初期値として別途加算する必要がある点に注意してください。

  ソースコード

import heapq
import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    adj = [[] for _ in range(N + 1)]
    for i in range(M):
        U = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        W = int(input_data[idx]); idx += 1
        adj[U].append((V, W))
        adj[V].append((U, W))
    
    toll = [0] * (N + 1)
    for j in range(K):
        L = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        toll[L] = C
    
    # Dijkstra with cost = sum of edge weights + sum of tolls at visited nodes
    # When we visit a node, we add its toll to the cost
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = toll[1]
    heap = [(dist[1], 1)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        if u == N:
            break
        for v, w in adj[u]:
            nd = d + w + toll[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    
    print(dist[N])

main()

---

この解説は claude4.6opus-thinking によって生成されました。