Overview

This problem asks us to find the shortest distance from vertex \(1\) to vertex \(N\) in a weighted directed graph.

Analysis

This problem is a classic “single-source shortest path problem” and can be efficiently solved using Dijkstra’s algorithm.

Naive approaches such as exhaustive search or breadth-first search (BFS) exist, but since the edges have weights, a simple BFS cannot determine the shortest distance. Additionally, since the number of edges can be up to \(2 \times 10^5\), using an algorithm with high computational complexity (such as the Floyd–Warshall algorithm with \(O(N^3)\)) will not meet the time limit.

Therefore, we take advantage of the property that all edge weights are non-negative and apply Dijkstra’s algorithm. By using a priority queue (heap), Dijkstra’s algorithm efficiently selects the vertex with the minimum cost and updates the shortest distances.

Algorithm

1. Represent the graph in adjacency list form.
2. Prepare an array dist to manage the shortest distance to each vertex, initialized to infinity (\(\infty\)). However, set the distance of the starting vertex (vertex \(1\)) to \(0\).
3. Add the starting vertex to the priority queue (heap) in the form (distance, vertex).
4. Repeat the following until the queue is empty:
   • Extract the vertex with the smallest distance from the queue.
   • For each edge extending from that vertex, if the new path is shorter, update dist and add it to the queue.
5. Finally, dist[N] contains the shortest distance from vertex \(1\) to vertex \(N\).

Example

For instance, suppose we have the following input:

4 5
1 2 2
1 3 5
2 3 1
2 4 7
3 4 3

In this case, the shortest path from vertex \(1\) to vertex \(4\) is \(1 \to 2 \to 3 \to 4\), with a distance of \(2 + 1 + 3 = 6\).

Complexity

• Time complexity: \(O((N + M) \log N)\)
• Space complexity: \(O(N + M)\)

Here, \(N\) is the number of vertices and \(M\) is the number of edges. Since each priority queue operation costs \(\log N\), the overall complexity is as stated above.

Implementation Notes

• Storing the graph as an adjacency list is efficient.

• Initialize distances using float('inf').

• By inserting tuples of (distance, vertex) into the priority queue, vertices are extracted in order of increasing distance.

• Since the same vertex may be inserted into the queue multiple times, when extracting a vertex, you need to check whether its shortest distance has already been updated.

  Source Code

import heapq
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    graph = [[] for _ in range(N + 1)]
    
    index = 2
    for _ in range(M):
        u = int(data[index])
        v = int(data[index + 1])
        c = int(data[index + 2])
        graph[u].append((v, c))
        index += 3
    
    # Dijkstra's algorithm
    dist = [float('inf')] * (N + 1)
    dist[1] = 0
    pq = [(0, 1)]  # (distance, node)
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
            
        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(dist[N])

if __name__ == "__main__":
    main()

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