Problem
It is the year of Olympics where athletes all over the world gathered at Paris to showcase their exceptional skills. One of the most exciting events of the Olympics is the Road Cycling Race, arranged across Paris, starting from the Olympic Village, referred to as checkpoint 1, ending at the stunning Olympic Stadium, referred to as checkpoint n.
To add an exciting challenge this year, the organizing committee has decided to not assign one single route. Instead, they provide each team with the city layout in the format of m roads between the n checkpoints to reach the Olympic Stadium. There is a complex network of these roads, some perfectly smooth, which take you from checkpoint u to checkpoint v very fast, whereas some are carved slower because of the terrain. The cyclists must navigate through these roads, choosing their paths carefully to reach the finish line in the shortest possible time.
You, being the coach representing the Indian team, must select the most efficient route and guide your cyclist to take the route with the fastest time to the Olympic Stadium. Your expertise along with the cyclist's skill is sure to bring in a Gold to the country this year.
Input
The first line of input contains two integers n, the number of checkpoints and m, the number of roads between these checkpoints. The next m lines each contain three integers u, v, and w where u and v are the checkpoints and w is the time required to reach checkpoint v from checkpoint u or vice-versa via one of the m roads.
Constraints
- 2 ≤ n ≤ 1000
- 0 ≤ m ≤ 1000
- 1 ≤ u, v ≤ n
- 1 ≤ w ≤ 104
Output
For each test case, print one integer, the minimum time required for the cyclist to reach the Olympic Stadium, checkpoint n starting from the Olympic Village, checkpoint 1. In the odd case that there doesn't exist any route from checkpoint 1 to checkpoint n, then print −1.
Example
Input:
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
Output:
5
Explanation:

As one can see from the city layout of the Road Cycling Race, when your cyclist starts from the Olympic Village at checkpoint 1, taking the roads marked by green, will lead them to the Olympic Stadium marked by checkpoint 5, the fastest within 1 + 3 + 1 = 5 units of time.
Solution
import heapq # Importing the heapq module to use the priority queue (min-heap)
def dijkstra(n, m, edges):
# Create a graph as an adjacency list
graph = [[] for _ in range(n+1)]
# We create an adjacency list where each index represents a checkpoint.
# Each checkpoint will store a list of tuples (neighbor, weight).
for u, v, w in edges:
graph[u].append((v, w)) # Add the edge from u to v with weight w
graph[v].append((u, w)) # Since the roads are bidirectional, also add from v to u
# Distance array to store the minimum distance to each checkpoint
dist = [float('inf')] * (n + 1)
# Initialize the distance to all checkpoints as infinity (unreachable)
# We will update these distances as we find shorter paths.
dist[1] = 0 # The distance to the starting checkpoint (1) is 0
# Priority queue to store the checkpoints for exploration
pq = [(0, 1)] # Start with checkpoint 1 at distance 0
while pq: # While there are nodes to explore in the priority queue
d, node = heapq.heappop(pq) # Pop the node with the smallest distance
if d > dist[node]:
# If the popped distance is greater than the known distance, skip it
continue
# Explore neighbors
for neighbor, weight in graph[node]:
new_dist = d + weight # Calculate the new distance to the neighbor
if new_dist < dist[neighbor]:
# If the new distance is shorter, update the distance
dist[neighbor] = new_dist
# Push the updated distance and neighbor into the priority queue
heapq.heappush(pq, (new_dist, neighbor))
# If the distance to the nth checkpoint is still infinity, return -1
return dist[n] if dist[n] != float('inf') else -1
# If we found a path to the last checkpoint (n), return the distance
# Otherwise, return -1 to indicate no such path exists
# Reading input
n, m = map(int, input().split())
# Read the number of checkpoints (n) and the number of roads (m)
edges = [tuple(map(int, input().split())) for _ in range(m)]
# Read the next m lines, each containing u, v, and w, representing an edge
# Output the result
print(dijkstra(n, m, edges))
# Call the Dijkstra function with the given inputs and print the result
Explanation
We start by importing the heapq
module, which provides an efficient implementation of the priority queue (min-heap) data structure. The dijkstra
function takes the number of checkpoints n
, the number of roads m
, and a list of edges as input. It returns the shortest path from the first checkpoint to the last checkpoint or -1
if no such path exists.
The function constructs a graph as an adjacency list, where each checkpoint is represented by an index, and each index stores a list of tuples representing the neighbors and their weights. The function initializes a distance array dist
to store the minimum distance to each checkpoint, with all distances initially set to infinity except for the starting checkpoint at index 1. It also initializes a priority queue pq
with the starting checkpoint and its distance.
The function then enters a loop to explore the checkpoints in the priority queue. It pops the checkpoint with the smallest distance from the queue and updates the distances to its neighbors if a shorter path is found. The updated distances and neighbors are pushed back into the priority queue for further exploration.
After exploring all possible paths, the function checks if the distance to the last checkpoint is still infinity. If it is, the function returns -1
to indicate that no path exists from the starting checkpoint to the last checkpoint. Otherwise, it returns the distance to the last checkpoint, which represents the shortest path.
The main part of the code reads the input values for the number of checkpoints and roads, as well as the edges between the checkpoints. It then calls the dijkstra
function with the input values and prints the result.
Time Complexity
The time complexity of the Dijkstra algorithm is O((n + m) log n)
, where n
is the number of checkpoints and m
is the number of roads. The algorithm explores each edge at most once and uses a priority queue to efficiently select the next checkpoint to explore based on the shortest distance.
Sample Solution Provided by Instructor