Overview

This problem asks you to find the shortest travel time from point \(1\) to point \(N\) in a situation where speed regulations double the travel time on certain roads. If the destination is unreachable, output \(-1\).

Analysis

• This problem is a “shortest path in a weighted undirected graph.”
  The weight (travel time) of each road is given, and only the regulated roads have their weights changed from \(W_i \rightarrow 2W_i\), so ultimately we just need to find the shortest distance on a “graph with finalized weights.”
• Naively “enumerating all paths and finding the shortest” is impossible. The number of paths grows exponentially, and with \(N, M \le 2 \times 10^5\), this is far too slow.
• Additionally, breadth-first search (BFS) can only guarantee correct shortest distances when “all edge weights are equal.” In this problem, \(W_i\) can be up to \(10^9\) and differs per edge, so BFS would result in WA.
• Since all weights are non-negative (\(W_i \ge 1\), so \(2W_i\) is also non-negative), we can use the standard Dijkstra’s algorithm.

As a concrete example, if a road’s normal travel time is \(5\) minutes and it is subject to regulation, that road’s weight becomes \(10\) minutes. The essence of the problem is to determine the actual weight of every road this way, then solve it as a shortest path problem.

Algorithm

1. Store the information \((U_i, V_i, W_i)\) for road \(i\) from the input.
2. Record the regulated road numbers \(C_1,\dots,C_K\) in a boolean array regulated (whether road \(i\) is subject to regulation).
3. Build an adjacency list:
   • Set the actual weight of road \(i\) as
     $\( w = \begin{cases} 2W_i & (\text{regulated})\\ W_i & (\text{otherwise}) \end{cases} \)$ and add it as an undirected edge to both g[U_i] and g[V_i].
4. Use Dijkstra’s algorithm to find the shortest distances dist from source \(1\).
   • Insert (distance, vertex) into a priority queue (heap), and finalize vertices in order of minimum distance.
   • If a popped element (d, u) is outdated information (d != dist[u]), skip it.
5. If dist[N] was never updated, the destination is unreachable, so output \(-1\); otherwise, output dist[N].

Complexity

• Time complexity: \(O((N+M)\log N)\)
  (Dijkstra’s algorithm: each edge relaxation is effective at most once, and each heap operation costs \(\log N\))
• Space complexity: \(O(N+M)\)
  (adjacency list, distance array, heap)

Implementation Notes

• Since the input is large, we read it all at once with sys.stdin.buffer.read() and split() it for fast processing.

• The regulated road numbers are \(1\)-indexed, so we subtract \(1\) to convert them to \(0\)-indexed to match the array.

• The shortest distance can become extremely large (\(W_i \le 10^9\), and there can be many edges), so we use a sufficiently large value like INF = 10**30.

• As a standard technique in Dijkstra’s algorithm, we skip outdated elements popped from the heap using if d != dist[u]: continue, reducing unnecessary exploration.

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    idx = 0
    N, M, K = data[idx], data[idx + 1], data[idx + 2]
    idx += 3

    U = [0] * M
    V = [0] * M
    W = [0] * M
    for i in range(M):
        U[i] = data[idx]
        V[i] = data[idx + 1]
        W[i] = data[idx + 2]
        idx += 3

    regulated = [False] * M
    for _ in range(K):
        c = data[idx] - 1
        idx += 1
        regulated[c] = True

    g = [[] for _ in range(N + 1)]
    for i in range(M):
        w = W[i] * 2 if regulated[i] else W[i]
        u = U[i]
        v = V[i]
        g[u].append((v, w))
        g[v].append((u, w))

    INF = 10**30
    dist = [INF] * (N + 1)
    dist[1] = 0
    pq = [(0, 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
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    ans = dist[N]
    print(-1 if ans >= INF else ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.