Shortest Routes I

import heapq

def dijkstra(n, graph):
    # Initialize distances with infinity
    dist = [float('inf')] * (n + 1)
    dist[1] = 0  # Starting city (Syrjälä) has a distance of 0
    
    # Priority queue (min-heap), stores (distance, node)
    pq = [(0, 1)]  # (distance to node, node)
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        # If we encounter a city with a larger distance, skip it
        if current_dist > dist[u]:
            continue
        
        # Process each neighbor v of city u
        for v, length in graph[u]:
            new_dist = current_dist + length
            if new_dist < dist[v]:  # Found a shorter path to city v
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    
    return dist[1:]  # Return distances from city 1 (Syrjälä)

# Input Parsing
n, m = map(int, input().split())

# Build the graph as an adjacency list
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))  # Flight from city a to city b with cost c

# Run Dijkstra's algorithm
shortest_distances = dijkstra(n, graph)

# Output the shortest distances from Syrjälä (city 1)
print(" ".join(map(str, shortest_distances)))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED