Graph Theory37 sections · 1633 units
Open in Course

CSES 1195 Flight Discount - Lessons

State expansion patterns

When you have a one-time action (like using a discount, picking up an item, or taking a special move), augment your state to track whether the action was used. You maintain separate distance arrays for each state variant. In this problem, dist[u][0] and dist[u][1]. In other problems, you might have dist[u][mask] where mask is a bitmask of collected items.

The algorithm structure is unchanged. You have more states to process. Each state represents a distinct scenario: arriving at the same node under different conditions. Dijkstra guarantees you find the best path for each scenario.