Overview

This is a problem of finding the shortest path from point \(1\) to point \(N\) on a weighted undirected graph. It is a typical single-source shortest path problem and can be solved using Dijkstra’s algorithm.

Analysis

Essence of the Problem

This problem asks us to find the shortest distance from vertex \(1\) to vertex \(N\) in a weighted undirected graph with \(N\) vertices and \(M\) edges. From the constraints, we can see that all edge weights (travel times) are positive (\(1 \leq C_i \leq 10^9\)).

Naive Approaches and Their Issues

• Exhaustive path search (DFS/BFS): One could enumerate all paths from point \(1\) to point \(N\) and choose the minimum, but the number of paths grows exponentially, leading to TLE (Time Limit Exceeded) when \(N\) or \(M\) is large.
• BFS (Breadth-First Search): BFS can find shortest paths in unweighted graphs, but since edge weights differ, simple BFS will not produce the correct answer, resulting in WA.

Solution

Since all edge weights are non-negative, Dijkstra’s algorithm is optimal. By using a priority queue (min-heap), we can efficiently determine the shortest distances.

Algorithm

The steps of Dijkstra’s algorithm are as follows:

1. Initialization: Set the distance of the source (point \(1\)) to \(0\) and the distance of all other points to \(\infty\). Insert \((0, 1)\) (distance, point number) into the priority queue.

2. Iteration: Repeat the following until the queue is empty:

   • Extract the element \((d, v)\) with the minimum distance from the queue.
   • If \(d > \text{dist}[v]\), a shorter path has already been finalized, so skip this element (an important pruning step).
   • For each vertex \(u\) adjacent to vertex \(v\), if \(d + w\) (where \(w\) is the edge weight) is less than the current \(\text{dist}[u]\), update \(\text{dist}[u]\) and add \((d + w, u)\) to the queue.

3. Result: If \(\text{dist}[N]\) remains \(\infty\), the destination is unreachable, so output -1. Otherwise, output \(\text{dist}[N]\).

Concrete Example

For example, with \(N=3, M=3\) and the following roads: - \(1 \to 2\) (travel time \(2\)), \(2 \to 3\) (travel time \(3\)), \(1 \to 3\) (travel time \(10\))

Dijkstra’s algorithm starts from point \(1\) with distance \(0\), and discovers point \(2\) (distance \(2\)) and point \(3\) (distance \(10\)). Next, it processes point \(2\) and updates the distance to point \(3\) to \(2 + 3 = 5 < 10\). The final answer is \(5\).

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Because priority queue operations (\(O(\log N)\)) occur for each vertex and each edge.
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) for the adjacency list representation of the graph, \(O(N)\) for the distance array, and at most \(O(M)\) for the priority queue.

Implementation Notes

• Pruning (if d > dist[v]: continue): If the distance extracted from the queue is greater than the already finalized distance, skip it. Without this, the same vertex would be processed multiple times, causing significant slowdown.

• Distance overflow: Since \(C_i\) can be up to \(10^9\) and there can be up to \(2 \times 10^5\) edges, the shortest distance can be approximately \(2 \times 10^{14}\). Python does not have integer overflow issues, but in C++ and similar languages, long long must be used.

• Using sys.stdin.readline: In Python, input tends to be slow, so sys.stdin.readline is used for faster input.

• 1-indexed adjacency list: Since point numbers range from \(1\) to \(N\), a list of size \(N+1\) is prepared so that indices can be used directly.

  Source Code

import heapq
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]
    
    while pq:
        d, v = heapq.heappop(pq)
        if d > dist[v]:
            continue
        for u, w in graph[v]:
            nd = d + w
            if nd < dist[u]:
                dist[u] = nd
                heapq.heappush(pq, (nd, u))
    
    print(dist[N] if dist[N] != INF else -1)

main()

---

This editorial was generated by claude4.6opus-thinking.