CSES 1195 Flight Discount - Transitions

Starting at state (u, $0$), you have two choices:

$1.$ Take edge u→v at full cost: move to state (v, $0$).

$2.$ Use coupon on edge u→v: move to state (v, $1$) at half cost. Starting at state (u, $1$), you have one choice:

$1.$ Take edge u→v at full cost: move to state (v, $1$).

This gives you $2N$ nodes and up to $3M$ edges in the state graph. Run standard Dijkstra on this expanded graph. The answer is min(dist[(N,0)], dist[(N,1)]).