Overview

This is a problem of finding the minimum cost path from intersection \(1\) to intersection \(N\) on a graph where tolls are assigned to intersections. The cost is the sum of “travel time” and “tolls of intersections passed through.”

Analysis

This problem is characterized by the fact that nodes (intersections) have weights, unlike simple shortest path search. In the standard Dijkstra’s algorithm, only edge weights are considered, but in this problem, each node also has a cost (toll).

Key Observations

• The toll at each node must be paid upon arriving at that node.
• Since the tolls at the source (intersection \(1\)) and destination (intersection \(N\)) are also included, the initial cost must be set to toll[1].
• Rather than simply considering only edge weights, we need to treat “cost to the current node + edge weight + toll of the next node” as the next cost.

Issues with a Naive Approach

For example, one might think of adding the toll of the adjacent node to every edge weight, but this is wasteful and also inaccurate (there is a possibility of double-counting when visiting the same node multiple times).

Solution

The appropriate approach is to extend Dijkstra’s algorithm to manage shortest distances with node costs included. Specifically: - Maintain the minimum cost to vertex \(u\) in dist[u]. - When moving from node \(u\) to adjacent node \(v\), the new cost is $\( \text{dist}[u] + \text{edge\_weight}(u, v) + \text{toll}[v] \)$ and we search while managing this with a heap.

Algorithm

This problem can be solved efficiently using Dijkstra’s algorithm.

Steps

1. Build the graph in adjacency list format.
2. Store the toll for each intersection in the array toll.
3. Run Dijkstra’s algorithm:
   • In the initial state, dist[1] = toll[1] (including the toll at the starting point)
   • Elements are inserted into the heap in the form (cost, node)
   • When transitioning from each node, update the cost by taking into account the toll of the next node
4. Output the cost when node \(N\) is reached.

Complexity

• Time complexity: \(O((N + M) \log N)\)
• Space complexity: \(O(N + M)\)

The priority queue (heap) operations in Dijkstra’s algorithm are performed at most \(N + M\) times, and each operation takes \(\log N\), resulting in the above overall complexity.

Implementation Notes

• Skip if the cost extracted from the heap has already been updated (standard technique)

• Since tolls are associated with each node, manage them separately from edge weights

• Don’t forget to include toll[1] in the initial cost

• Since the graph is undirected, be careful to add edges in both directions

  Source Code

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

---

This editorial was generated by qwen3-coder-480b.