Overview

This is a problem where, in addition to road travel times, there is a “toll charged every time you pass through an intersection.” We need to find the minimum cost path from intersection \(1\) to \(N\) in this graph. Tolls are also paid at the starting and ending points.

Analysis

• This is essentially a shortest path problem.
  However, unlike the usual shortest path where “edges (roads) have weights,” this problem also has “costs (tolls) on vertices (intersections).”
• A naive approach of “enumerating all paths and taking the minimum” would cause the number of paths to explode and is completely infeasible for \(N, M \le 2\times 10^5\).
• The key insight is that vertex costs can be incorporated into edge transitions as “the cost of entering the next vertex.”
  When going from intersection \(u\) to \(v\) via road \((u,v)\) (with time \(w\)), the additional cost is $\( w + \text{toll}[v] \)$
• Since the toll at the starting point is also required, the initial value is set as $\( \text{dist}[1] = \text{toll}[1] \)\( to start (the toll at the destination is also naturally handled, as \)\text{toll}[N]\( is added when entering \)N$ from somewhere).

With this formulation, all weights are non-negative (\(w\ge 1\), \(\text{toll}\ge 0\)), so Dijkstra’s algorithm can be directly applied.

Algorithm

1. Build an undirected graph using an adjacency list.
2. Prepare a toll array toll for each intersection, setting it to \(0\) for vertices without tolls.
3. Run Dijkstra’s algorithm.
   
   • dist[i] = minimum cost to reach intersection \(i\) from intersection \(1\)
     
   • Initialization: dist[1] = toll[1]
   • Extract vertex u from the priority queue, and for each neighbor v, relax using $\( \text{nd} = \text{dist}[u] + w(u,v) + \text{toll}[v] \)$
4. Output dist[N].

(Example) If the travel time from \(1 \to 3\) is \(5\), and the tolls are \(\text{toll}[1]=2, \text{toll}[3]=4\), then the cost is \(2 + 5 + 4 = 11\). This is simply the sum of “passing through 1” + “road” + “passing through 3.”

Complexity

• Time complexity: \(O((N+M)\log N)\) (Dijkstra’s algorithm + priority queue)
• Space complexity: \(O(N+M)\) (graph, distance array, queue)

Implementation Notes

• Don’t forget the toll at the starting point — set dist[1] = toll[1] (setting this to \(0\) will result in WA).

• In Dijkstra’s algorithm, it is typical to skip when d != dist[u] for a pair (d, u) extracted from the priority queue, as it represents outdated information.

• You can break as soon as u == N is finalized (at the point it is extracted from the queue), which is correct and provides a slight speedup (this is also done in the code).

  Source Code

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

This editorial was generated by gpt-5.2-high.