Overview

This problem asks us to find the shortest path in a graph where edges between specific vertices have costs that can change. There is a constraint that the cost of certain edges is doubled.

Analysis

First, this is a typical “shortest path search in a weighted graph” problem, and Dijkstra’s algorithm is effective.

However, simply applying Dijkstra’s algorithm is not sufficient. This is because for some roads (edges), the travel time becomes twice the normal amount. In other words, the cost changes depending on “which edges were traversed,” so simply managing distances per vertex alone is not enough to find the correct answer.

That said, in this problem, we do not need to consider extended states such as “whether a node has been visited or not.” This is because the cost of each edge is known in advance as an attribute of the edge itself, so when processing edges within Dijkstra’s algorithm, we can simply check “whether this edge is subject to speed regulation” and appropriately double the cost in our calculation.

Additionally, given the constraints \(N, M \leq 2 \times 10^5\), a naive brute-force search would not be fast enough, so we need to use an efficient algorithm like Dijkstra’s algorithm.

Furthermore, there is a possibility that vertex \(N\) is unreachable from vertex \(1\), in which case we need to output -1.

Algorithm

We use Dijkstra’s algorithm.

1. Store each edge’s information as (u, v, w), and in the adjacency list representation, also store the edge index alongside each edge.
2. Keep the set of edge numbers subject to speed regulation, so we can quickly determine whether a given edge is regulated.
3. Search using Dijkstra’s algorithm, managing shortest distances from the source (vertex \(1\)):
   • Use a priority queue to extract and process the node with the current minimum cost.
   • For edges extending from the extracted node, if the edge is subject to regulation, double the cost for the transition.
4. Output the value once the shortest distance to vertex \(N\) is determined.
5. If vertex \(N\) is still unreachable after the search completes, output -1.

Complexity

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

This is the typical complexity of Dijkstra’s algorithm, with the logarithmic factor coming from the priority queue implementation.

Implementation Notes

• When storing edge information, also save the index so that we can later determine whether the edge is subject to speed regulation.

• Align the edge numbers for speed-regulated edges to 0-indexed to prevent implementation mistakes.

• In the Dijkstra’s algorithm implementation, it is efficient to add pruning to avoid reprocessing nodes that have already been updated.

• Be careful not to forget handling the unreachable case.

  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
    
    edges = []
    graph = [[] for _ in range(N+1)]
    
    for i in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        edges.append((u, v, w))
        graph[u].append((v, i))
        graph[v].append((u, i))
    
    speed_limited = set()
    if K > 0:
        for _ in range(K):
            c = int(data[idx]) - 1; idx += 1  # 0-indexed
            speed_limited.add(c)
    
    # Dijkstra: (distance, node)
    dist = [1 << 60] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        if u == N:
            print(d)
            return
        for v, edge_idx in graph[u]:
            edge = edges[edge_idx]
            cost = edge[2] * 2 if edge_idx in speed_limited else edge[2]
            nd = d + cost
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    
    print(-1)

if __name__ == "__main__":
    main()

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