Overview

This is a problem of finding the shortest distance (minimum total time) from point \(1\) to point \(N\) in a weighted (travel time) undirected graph. If the destination is unreachable, output -1.

Analysis

If we regard each location as a vertex, each road as an edge, and each travel time \(C_i\) as the edge weight, this becomes a “shortest path problem from source \(1\) to destination \(N\).”

• Key observation: Since all travel times \(C_i\) are at least \(1\) (positive weights), the shortest path can be efficiently found using Dijkstra’s algorithm.
• Why naive approaches fail:
  • Exploring all paths (e.g., enumerating all paths with DFS) is infeasible because the number of paths explodes.
  • BFS only guarantees the shortest path when all edge weights are the same. Since \(C_i\) varies in this problem, BFS is inappropriate.
  • Bellman-Ford has \(O(NM)\) complexity, which at maximum would be \(10^5 \times 2\times 10^5\), making it impractical.
• Solution: Using Dijkstra’s algorithm with a priority queue (heap), we always process the candidate that can be confirmed as having the shortest distance so far, enabling fast distance updates.

(Example)
If \(1 \to 2\) takes 100 minutes, \(1 \to 3\) takes 1 minute, and \(3 \to 2\) takes 1 minute, BFS would tend to pick \(1\to2\) first since it has fewer edges, but the shortest time is \(1\to3\to2\) at 2 minutes. Because edges have weights, Dijkstra’s algorithm is necessary.

Algorithm

We use Dijkstra’s algorithm (shortest path with positive weights).

1. Build the graph using an adjacency list (since it’s undirected, add edges in both directions).
2. Prepare a distance array dist with dist[1]=0 and all others set to a sufficiently large value (INF).
3. Start by inserting (distance, vertex) into the priority queue.
4. Extract the element (d, v) with the minimum distance from the queue.
   • If d != dist[v], this is outdated information (a shorter update has already been recorded), so skip it.
5. For each edge (v -> to, weight w) from vertex v:
   • If nd = d + w is less than dist[to], update it and add (nd, to) to the queue.
6. If dist[N] remains INF, the destination is unreachable, so output -1; otherwise, output dist[N].
   • In the code, we terminate early when v == N is extracted, which provides a slight speedup (since in Dijkstra’s algorithm, the distance is finalized at the time of extraction).

Complexity

• Time complexity: \(O\big((N+M)\log N\big)\)
  (Each edge relaxation occurs at most a few times, and each heap operation costs \(\log N\))
• Space complexity: \(O(N+M)\)
  (Adjacency list, distance array, and heap)

Implementation Notes

• Since the input is large, we use sys.stdin.buffer.read() to read all input at once for speedup.

• Since the graph is undirected, we add both g[a].append((b,c)) and g[b].append((a,c)).

• The element (d, v) extracted from the heap may be outdated, so the standard technique is to discard it with if d != dist[v]: continue.

• The maximum distance can result from summing many edges of weight up to \(10^9\), so INF should be set sufficiently large, such as 10**30.

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        a = next(it); b = next(it); c = next(it)
        g[a].append((b, c))
        g[b].append((a, c))

    INF = 10**30
    dist = [INF] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]

    while pq:
        d, v = heapq.heappop(pq)
        if d != dist[v]:
            continue
        if v == N:
            break
        for to, w in g[v]:
            nd = d + w
            if nd < dist[to]:
                dist[to] = nd
                heapq.heappush(pq, (nd, to))

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

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.