Overview

This problem requires finding the shortest path (minimum cost) from point \(1\) to point \(N\), considering both road travel times (edge weights) and intersection tolls (vertex weights).

Analysis

Dijkstra’s algorithm, a well-known shortest path algorithm, typically handles only edge weights (road travel times). However, in this problem, costs are also incurred when passing through vertices (intersections).

The key insight is to consider the cost of the action “moving from intersection \(u\) to adjacent intersection \(v\)” as (road travel time \(W\)) + (toll at destination intersection \(v\), \(C_v\)).

However, with this approach alone, the “toll at the starting point (intersection \(1\))” would be missed in the calculation. Since the problem statement specifies that “tolls are also added if the starting point or destination has a toll area,” we can correctly compute the answer by setting the initial state — “the cost upon reaching intersection \(1\)” — to “the toll at intersection \(1\).”

Since all edge weights (road travel times) and vertex weights (tolls) are non-negative, Dijkstra’s algorithm can be applied to solve this problem efficiently.

Algorithm

We use Dijkstra’s algorithm for solving the single-source shortest path problem on a weighted graph.

1. Initialization:
   • Initialize an array dist that holds the minimum cost to each intersection with infinity (e.g., \(10^{18}\)).
   • Set dist[1] to “the toll at intersection \(1\).”
   • Prepare a priority queue (heap) and add (dist[1], 1) to it.
2. Exploration:
   • Extract the intersection \(u\) with the minimum cost \(d\) from the queue.
   • If d > dist[u], this information is outdated, so skip it.
   • For each intersection \(v\) adjacent to intersection \(u\) (with road weight \(w\)), perform the following calculation:
     • new cost = d + w + (toll at intersection v)
     • If new cost < dist[v], update dist[v] and add (new cost, v) to the queue.
3. Termination:
   • The value of dist[N] when intersection \(N\) is reached, or when the queue becomes empty, is the answer.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • This is the complexity of Dijkstra’s algorithm using a priority queue. Each edge is examined at most once, and each insertion/extraction operation on the queue costs \(O(\log N)\).
• Space complexity: \(O(N + M)\)
  • This is needed for the graph in adjacency list format, the cost array for each vertex, and the toll array.

Implementation Notes

• Storing tolls: Since not all intersections have toll areas, it is efficient to create an array tolls with a default value of \(0\) and overwrite it with the information for the given \(K\) locations.

• Handling large values: Since \(N, M\) can be up to \(2 \times 10^5\) and each cost can be up to \(10^9\), the total cost can exceed \(10^{14}\). The value used as infinity in the program must be set sufficiently large.

• Fast I/O: Since \(N, M\) can be large, in Python it is beneficial to read all input at once using sys.stdin.read().split() to improve execution speed.

  Source Code

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()

---

This editorial was generated by gemini-3-flash-thinking.