I am trying to solve the following code challenge
In a world with a total of N cities and M flight routes, each with a different ticket price, you are travelling from City A to City B, with the possibility of making one flight free, while all other flights must be paid for at their regular prices.
Constraints:
N, M <= 10^5
How to do that based on Dijkstra's algorithm?
When I traverse all cities to find out which ones to delete, it is taking too much time.
How to do that based on Dijkstra's algorithm? When I traverse all cities to find out which ones to delete, it is taking too much time.
Dijkstra's algorithm doesn't involve deleting nodes, nor does it always require to visit all nodes, although that might happen.
The trick here is to maintain state: remember for each entry in the priority queue (typical for Dijktra's algorithm) whether that entry corresponds to a route that includes a free flight or not. Then, when you pop an entry from the queue, produce the flights from that city, and if no free flight was used, then also produce free flights in addition to the paid flights from that city.
That's it. All the rest is standard Dijkstra's algorithm.