#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-shortest-paths/flight-discount-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/mixed-practice-shortest-paths/flight-discount-implementation

Repovive

CSES 1195 Flight Discount - Implementation - Mixed Practice - Shortest Paths | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

CSES 1195 Flight Discount - Implementation

(State Dijkstra)

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])