Overview

This problem asks us to find the shortest distance from vertex \(1\) to vertex \(N\) in a weighted undirected graph. If vertex \(N\) is unreachable, we output \(-1\).

Analysis

This problem is a classic “shortest path search” problem where each edge in the graph has a travel time associated with it. In such cases, exhaustive search (e.g., depth-first search) would result in extremely large computational complexity and is not practical.

A straightforward approach would be breadth-first search (BFS), but this is only effective when all edge weights are equal. However, since each edge has a different weight (time) in this problem, simple BFS cannot find the shortest time.

Therefore, Dijkstra’s Algorithm is well-suited for this problem. Dijkstra’s algorithm can efficiently find the single-source shortest path in a graph with non-negative edge weights.

Additionally, to handle the case where the destination is unreachable, we need to check whether the shortest distance to vertex \(N\) has not been updated (i.e., remains at its initial value).

Algorithm

We use Dijkstra’s algorithm. The procedure is as follows:

1. Prepare an array dist to manage the shortest distance to each vertex, initialized to infinity (float('inf')). However, the distance to the starting point (vertex \(1\)) is set to \(0\).
2. Use a priority queue (heap) to manage the current vertex and the shortest distance to it.
3. Extract the vertex with the smallest distance from the queue, and for each adjacent vertex, if a shorter path is found, update dist and add it to the queue.
4. When vertex \(N\) is reached, the distance at that point is the answer.
5. If vertex \(N\) cannot be reached after all exploration is complete, output -1.

Complexity

• Time complexity: \(O(M \log N)\)
  　→ Each edge is processed at most once, and insertion/extraction from the priority queue takes \(\log N\).
• Space complexity: \(O(N + M)\)
  　→ The adjacency list representation of the graph requires \(O(N + M)\).

Implementation Notes

• Since vertex numbers start from \(1\), it is convenient to internally convert them to \(0\) through \(N-1\).

• Store (distance, vertex) tuples in the heap so that vertices are extracted in order of increasing distance.

• To avoid reprocessing already-finalized vertices, we need to skip when dist[u] < d.

• A slight speedup is possible by outputting the answer immediately when the shortest path is found.

  Source Code

import heapq
import sys

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

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.