Overview

This is a shortest path problem from point \(1\) to point \(N\). We find the shortest time using Dijkstra’s algorithm on a weighted graph consisting of one-way roads.

Analysis

Problem Setup

• There are \(N\) points and \(M\) one-way roads
• Each road has a travel time (cost)
• We want to find the shortest time from point \(1\) to point \(N\)

Problems with Naive Approaches

If we try all paths using exhaustive search (DFS/BFS), the number of paths grows exponentially, causing TLE (Time Limit Exceeded) when \(N\) or \(M\) is large.

For example, in a nearly complete graph, the number of paths can be \(O(N!)\).

Solution

We use Dijkstra’s algorithm. This algorithm efficiently solves the single-source shortest path problem when edge weights are non-negative.

In this problem, since \(C_i \geq 1\), all edge weights are positive, making Dijkstra’s algorithm applicable.

Algorithm

Dijkstra’s algorithm works as follows:

1. Initialization: Set the distance to the source (point \(1\)) to \(0\), and all other points to \(\infty\)
2. Priority Queue: Used to efficiently extract the vertex with minimum distance
3. Iteration:
   • Extract the vertex \(u\) with minimum distance from the queue
   • For each edge \((u, v)\) from \(u\), check if we can update the distance to \(v\)
   • If we can update, add the new distance to the queue

Example: N=4, Roads: (1→2, time 3), (1→3, time 5), (2→4, time 2), (3→4, time 1)

Initial state: dist = [∞, 0, ∞, ∞, ∞]  (index 0 is unused)

Step 1: Process vertex 1 → dist[2]=3, dist[3]=5
Step 2: Process vertex 2 → dist[4]=3+2=5
Step 3: Process vertex 3 → dist[4]=min(5, 5+1)=5 (no update)

Answer: dist[4] = 5

Complexity

• Time Complexity: \(O((N + M) \log N)\)

  • Each vertex is extracted from the priority queue at most once
  • Each edge is relaxed at most once
  • Heap operations are \(O(\log N)\)

• Space Complexity: \(O(N + M)\)

  • Graph adjacency list: \(O(M)\)
  • Distance array: \(O(N)\)
  • Priority queue: up to \(O(M)\) (when duplicates exist)

Implementation Notes

1. Skip Processing: if d > dist[u]: continue

   • The same vertex may be added to the queue multiple times with different distances
   • Skip if already processed with a shorter distance to avoid unnecessary computation

2. Early Termination: if u == N: return

   • We can terminate immediately once the goal point is finalized (due to Dijkstra’s property, the shortest distance is finalized when first extracted from the queue)

3. Distance Data Type: 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 up to about \(2 \times 10^{14}\)

   • In Python, there’s no worry about integer overflow, but in other languages, use 64-bit integer types

4. Using defaultdict: Prevents errors when accessing non-existent vertices and makes the code more concise

Source Code

import heapq
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    
    # Build graph with adjacency list
    graph = defaultdict(list)
    for _ in range(M):
        u, v, c = map(int, input().split())
        graph[u].append((v, c))
    
    # Dijkstra's algorithm
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = 0
    
    # (distance, vertex)
    pq = [(0, 1)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        # Skip if a shorter path has already been found
        if d > dist[u]:
            continue
        
        # Terminate when reaching the goal
        if u == N:
            print(dist[N])
            return
        
        for v, cost in graph[u]:
            new_dist = d + cost
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    
    print(dist[N])

solve()

---

This editorial was generated by claude4.5opus.