Overview

This problem is a shortest path problem on a graph, asking for the shortest path from point 1 to point N. Given a road network where the time required to traverse each road is known, we need to find the minimum travel time.

Analysis

Since the number of points N can be up to \(10^5\) and the number of roads M can be up to \(2 \times 10^5\), the graph is large-scale, so simple depth-first search or breadth-first search cannot solve it efficiently. In particular, since the edge weights (travel times) are not uniform, a simple BFS cannot yield the correct solution.

If we consider a naive approach of exhaustively searching all paths, the number of paths grows explosively, making it infeasible to compute within a realistic time frame. For such large-scale graphs, an efficient shortest path algorithm is required.

Algorithm

Dijkstra’s algorithm is well-suited for this problem. Dijkstra’s algorithm efficiently solves the single-source shortest path problem on graphs with non-negative edge weights.

The steps of the algorithm are as follows: 1. Initialize an array to store distances from the source (point 1) — set the source to 0 and all others to infinity 2. Use a priority queue (min-heap) to select the unfinalized point with the shortest distance 3. For each neighboring point reachable from the selected point, update the distance if a shorter path is found 4. Repeat until the shortest distances to all points are finalized, or until the distance to the destination (point N) is finalized

Dijkstra’s algorithm is a type of greedy algorithm that efficiently finds the shortest path by selecting the nearest point at each step.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Each edge is processed at most once, and each heap operation takes \(\log N\) time
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) for the graph representation, \(O(N)\) for the distance array, and \(O(N)\) for the heap

Implementation Notes

• Use sys.stdin.read() for fast input processing to handle large-scale inputs

• Represent the graph in adjacency list format to improve memory efficiency

• Use a priority queue (heap) to efficiently select the next node to process

• Improve efficiency by skipping nodes that have already been finalized when updating distances

• Handle the unreachable case by outputting -1 when the distance remains infinity

  Source Code

import heapq
import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    m = int(data[1])
    
    graph = [[] for _ in range(n+1)]
    index = 2
    for i in range(m):
        a = int(data[index])
        b = int(data[index+1])
        c = int(data[index+2])
        index += 3
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    INF = float('inf')
    dist = [INF] * (n+1)
    dist[1] = 0
    
    heap = [(0, 1)]
    
    while heap:
        current_time, current_node = heapq.heappop(heap)
        
        if current_time > dist[current_node]:
            continue
            
        for neighbor, time in graph[current_node]:
            new_time = current_time + time
            if new_time < dist[neighbor]:
                dist[neighbor] = new_time
                heapq.heappush(heap, (new_time, neighbor))
    
    if dist[n] == INF:
        print(-1)
    else:
        print(dist[n])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.