概要

道路の移動時間に加えて「交差点を通るたびに通行料がかかる」グラフで、交差点 \(1\) から \(N\) までの最小コスト経路を求める問題です。通行料は出発点・到着点でも支払います。

考察

• これは本質的に最短経路問題です。
  ただし通常の最短経路は「辺（道路）に重み」があるのに対し、この問題では「頂点（交差点）にもコスト（通行料）」があります。
• 素朴に「全ての経路を列挙して最小を取る」ような方法は、経路数が爆発して \(N, M \le 2\times 10^5\) では到底間に合いません。
• 重要な気づきは、頂点コストは“次に到達する頂点に入るコスト”として辺の遷移に組み込めることです。
  交差点 \(u\) から道路 \((u,v)\)（時間 \(w\)）で \(v\) に行くとき、追加コストは $\( w + \text{toll}[v] \)$ となります。
• 出発点の通行料も必要なので、初期値は $\( \text{dist}[1] = \text{toll}[1] \)\( としてスタートします（到着点の通行料も、どこかから \)N\( に入るときに \)\text{toll}[N]$ が加算されるので自然に処理できます）。

このようにすると、すべての重みが非負（\(w\ge 1\), \(\text{toll}\ge 0\)）なので ダイクストラ法がそのまま使えます。

アルゴリズム

1. 隣接リストで無向グラフを構築する。
2. 各交差点の通行料配列 toll を用意し、該当しない頂点は \(0\) にする。
3. ダイクストラ法を行う。
   
   • dist[i] = 交差点 \(1\) から \(i\) へ到達する最小コスト
     
   • 初期化：dist[1] = toll[1]
   • 優先度付きキューから頂点 u を取り出し、各隣接 v について $\( \text{nd} = \text{dist}[u] + w(u,v) + \text{toll}[v] \)$ で緩和する。
4. dist[N] を出力する。

（例）もし \(1 \to 3\) に時間 \(5\)、通行料が \(\text{toll}[1]=2, \text{toll}[3]=4\) なら、コストは \(2 + 5 + 4 = 11\) になります。これは「最初に 1 を通る」＋「道路」＋「3 を通る」をそのまま足した形です。

計算量

• 時間計算量: \(O((N+M)\log N)\)（ダイクストラ法＋優先度付きキュー）
• 空間計算量: \(O(N+M)\)（グラフ・距離配列・キュー）

実装のポイント

• 出発点の通行料を忘れずに dist[1] = toll[1] とする（ここが \(0\) だと WA）。

• ダイクストラ法では典型的に、優先度付きキューから取り出した (d, u) について d != dist[u] なら古い情報なのでスキップします。

• u == N が確定した時点（キューから取り出した時点）で break しても正しく、少し高速化できます（コードでも実施）。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it); M = next(it); K = next(it)

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next(it); v = next(it); w = next(it)
        g[u].append((v, w))
        g[v].append((u, w))

    toll = [0] * (N + 1)
    for _ in range(K):
        l = next(it); c = next(it)
        toll[l] = c

    INF = 10**30
    dist = [INF] * (N + 1)
    dist[1] = toll[1]
    pq = [(dist[1], 1)]

    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        if u == N:
            break
        for v, w in g[u]:
            nd = d + w + toll[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    print(dist[N])

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。