Overview

This is a problem of finding the shortest arrival time from point \(1\) to point \(N\) in a weighted (travel time) directed graph. Since all edge weights are positive, it can be solved using Dijkstra’s algorithm.

Analysis

If we treat each location as a vertex and each road as a directed edge “\(U \rightarrow V\) with cost \(C\)”, this problem is exactly the “shortest path problem from source \(1\) to destination \(N\)”.

Naively “enumerating all paths and taking the shortest” is impractical, as the number of paths explodes with each branch. Also, BFS (Breadth-First Search) finds the shortest path in terms of “number of edges (ignoring costs)”, but since the cost \(C_i\) is not necessarily \(1\) in this problem, it won’t give the correct answer (e.g., if there’s a single edge with cost 100 and a two-edge path with cost 1+1, BFS would choose the single edge).

The key observation is as follows:

• All costs are positive (\(C_i \ge 1\))
  → The property “a confirmed shortest distance is never updated later” holds
  → Dijkstra’s algorithm using a priority queue is applicable, and it runs efficiently even for \(N=10^5, M=2\times10^5\)

Algorithm

We use Dijkstra’s algorithm to find the shortest time dist to each location.

1. Build an adjacency list g[u] = [(v, c), ...] (since edges are directed, add only one direction).
2. Initialize dist[1] = 0, and all others to a sufficiently large value (INF).
3. Insert (0, 1) into a priority queue (min-heap).
4. Extract (d, u), the vertex with the current smallest distance, from the queue.
   • If d != dist[u], this is outdated information (it was later updated with a shorter distance), so skip it.
5. For each edge (u -> v, w) from u, compute nd = d + w.
   • If nd < dist[v], update dist[v] = nd and insert (nd, v) into the queue.
6. Repeating this process, dist[N] will ultimately be the shortest time.
   • In the code, we terminate early when u == N (at that point dist[N] is confirmed), which provides a slight speedup.

Simple example: - \(1 \to 2\) (5), \(1 \to 3\) (2), \(3 \to 2\) (1)
The shortest path is \(1 \to 3 \to 2\) with \(2+1=3\).
Dijkstra’s algorithm correctly finds this by “first confirming vertex 3 at distance 2 → then updating vertex 2 to distance 3 from there”.

Complexity

• Time complexity: \(O((N+M)\log N)\)
  (Each edge relaxation causes at most one update, and each heap operation costs \(\log N\))
• Space complexity: \(O(N+M)\)
  (Adjacency list, distance array, and heap)

Implementation Notes

• Use an adjacency list (since \(M\) is large, an adjacency matrix is infeasible).

• Set INF to a value sufficiently larger than the maximum possible distance (here, 10**30).
  The maximum cost is \(10^9\), and a path can have at most \(N-1\) edges, so distances can reach the order of \(10^{14}\).

• When extracting (d, u) from the heap, discard it if it doesn’t match the current dist[u] (if d != dist[u]: continue). Without this, the same vertex gets processed multiple times, causing slowdowns.

• Since the input is large, reading it all at once with sys.stdin.buffer.read() is faster.

  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):
        u = next(it); v = next(it); c = next(it)
        g[u].append((v, c))

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

    print(dist[N])

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.