Trick 2: How to get rid of TLE for BFS algorithm?

787. Cheapest Flights Within K Stops

I am going to compare the BFS solution for leetcode 787 Cheapest Flights Within K Stops.

The naive BFS solution will get TLE.

https://github.com/liketheflower/leet_code_jimmy/blob/master/dfs_bfs/787/bfs_tle.py

If we prune the to be explored nodes by current minimum total price, then we can get rid of TLE.

BFS solution (116 ms)

https://github.com/liketheflower/leet_code_jimmy/blob/master/dfs_bfs/787/bfs.py

Thanks for reading. Hope it helps.

Reference:

https://leetcode.com/problems/cheapest-flights-within-k-stops/