CSES 1195 Flight Discount - State-Space Graphs

You cannot run Dijkstra on the original graph. The best path depends on whether you have used the coupon yet.

Create a state-space graph with two copies of each node: (city, used_coupon). State (c, $0$) means at city c with coupon unused. State (c, $1$) means coupon already used.

Run Dijkstra on this expanded state graph. The answer is the minimum of distances to both end states. This doubles the number of nodes but keeps the same $O((N+M) \log N)$ complexity.