Overview

This is a problem of finding the shortest path from point 1 to point N under the condition that some roads take twice the normal time to traverse.

Analysis

This problem adds the constraint “specific roads have their cost doubled” to a standard shortest path problem. Since each road has two possible costs (normal and restricted), we can solve it by simply applying Dijkstra’s algorithm. We record the shortest distance to each vertex while calculating the appropriate cost based on the road’s state (whether it is subject to restrictions or not).

Algorithm

We use Dijkstra’s algorithm to find the shortest path. For each move from a vertex to an adjacent vertex, we determine whether the road being used is subject to speed restrictions (one of the \(K\) roads given in the input) and calculate the corresponding cost.

1. Build the graph in adjacency list format (storing tuples of (adjacent vertex, weight, road ID) for each vertex)
2. Store the road IDs subject to speed restrictions in a set
3. Execute Dijkstra’s algorithm:
   • Initialize the distance to the source (point 1) as 0, and all others as a sufficiently large value
   • Use a priority queue to select the vertex with the shortest distance among unfinalized vertices
   • For each edge extending from the selected vertex, check whether the road ID is in the restricted set
   • If restricted, double the cost; otherwise, calculate the new distance using the normal cost
   • If the calculated distance is shorter than the current distance, update it and add to the queue

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • This is the standard complexity of Dijkstra’s algorithm. Each vertex and edge is processed at most once, and priority queue operations take \(\log N\) time.
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) is needed for the graph representation, \(O(N)\) for the distance array, and \(O(N)\) for the priority queue.

Implementation Notes

• Use a set data structure for fast lookup of whether a road ID is subject to restrictions

• Use a large number (\(10^{18}\)) as infinity

• Since the input data can be large, read it all at once using sys.stdin.read()

• To prevent redundant processing of the same vertex in Dijkstra’s algorithm, only add to the queue when the distance is actually updated

  Source Code

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it)); k = int(next(it))
    
    graph = [[] for _ in range(n+1)]
    edges = {}
    
    for i in range(1, m+1):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        edges[i] = (u, v, w)
        graph[u].append((v, w, i))
        graph[v].append((u, w, i))
    
    restricted = set()
    if k > 0:
        for _ in range(k):
            c = int(next(it))
            restricted.add(c)
    
    INF = 10**18
    dist = [INF] * (n+1)
    dist[1] = 0
    heap = [(0, 1)]
    
    while heap:
        time, node = heapq.heappop(heap)
        if time != dist[node]:
            continue
        if node == n:
            break
            
        for neighbor, w, edge_id in graph[node]:
            if edge_id in restricted:
                new_time = time + 2 * w
            else:
                new_time = time + w
                
            if new_time < dist[neighbor]:
                dist[neighbor] = new_time
                heapq.heappush(heap, (new_time, neighbor))
                
    if dist[n] == INF:
        print(-1)
    else:
        print(dist[n])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.