CSES 1671 Shortest Routes I - Implementation Notes

Use a min-heap ordered by distance:

function dijkstra(n, adj, start):
    dist = array of size n + 1, all infinity
    dist[start] = 0
    pq = min-heap with (0, start)

    while pq is not empty:
        (d, u) = pq.pop()
        if d > dist[u]:
            continue
        for (v, w) in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pq.push((dist[v], v))

    return dist

Time: $O((N + M) \log N)$. Space: $O(N + M)$.