CSES 1195 Flight Discount - Implementation

Use $2D$ state for Dijkstra:

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

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

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