✈️ You’ve got one chance to use a discount on a flight — where do you use it to minimize your total travel cost?
📄 𝐍𝐨𝐭𝐞𝐬: https://github.com/yash7xm/cp_notes/tree/master/cses/graphs
In this video, we solve the Flight Discount problem from the CSES Problem Set using a smart modification of Dijkstra’s Algorithm. We introduce the concept of stateful shortest paths, where each node is visited in two states: before using the discount and after using it.
We walk you through how to implement a 2D distance array dist[node][state], why a priority queue of tuples is needed, and how to make optimal decisions under constraints. This is a real-world simulation of how algorithms adapt to dynamic conditions — a must-know trick in advanced competitive programming.
If you're looking to level up your graph skills and understand how to extend classic algorithms to new problems, this one's for you.
#ModifiedDijkstra #GraphAlgorithms #CSES #FlightDiscount #CompetitiveProgramming
