CSES 1195 Flight Discount - Implementation

Here is the solution:

function flightDiscount(n, edges):
    adj = array of n + 1 empty lists
    for (u, v, price) in edges:
        adj[u].append((v, price))

    dist = 2D array of size (n + 1) x 2, all infinity
    dist[1][0] = 0
    pq = min-heap with (0, 1, 0)

    while pq is not empty:
        (cost, u, used) = pq.pop()
        if cost > dist[u][used]:
            continue
        for (v, price) in adj[u]:
            if cost + price < dist[v][used]:
                dist[v][used] = cost + price
                pq.push((dist[v][used], v, used))
            if used == 0 and cost + price / 2 < dist[v][1]:
                dist[v][1] = cost + price / 2
                pq.push((dist[v][1], v, 1))

    return min(dist[n][0], dist[n][1])

This runs in $O((V + E) \log V)$ time and uses $O(V)$ space.