I dont get how incrementing the route_len by 1 makes sense cause we would then be finding gate number of stops rather than the number of buses taken right?
I think the understanding is that the route length is only incremented when we have a new bus to travel in, i.e one that is not in v_buses - so when you increment 1 you're incrementing the number of buses you've taken in that path.
"Least number of buses" is not the same as "shortest path or least number of stops", my understanding is we are trying to find a path with least switch between buses, I wonder why BFS would work
Typically you use BFS for when you want the shortest path, DFS for when you need to explore all paths. If the problem can be solved using either, I always prefer BFS because I find it easier to code and you don’t have to worry about overflow in extreme cases
@@crackfaang I have optimized it by: 1 - check if the target exists before you started BFS (case #44?), 2 - check for visited before adding anything into the queue. This fixed all TLE problems for me
This is so well explained and neatly written. Thanks a ton
No need to store the route length inside the queue. Just record the route_len as a variable that gets incremented for every queue iteration
Your explanation is great.
I dont get how incrementing the route_len by 1 makes sense cause we would then be finding gate number of stops rather than the number of buses taken right?
I think the understanding is that the route length is only incremented when we have a new bus to travel in, i.e one that is not in v_buses - so when you increment 1 you're incrementing the number of buses you've taken in that path.
How come we make an adjacency list of bus stops to bus routes rather than bus stops to other bus stops?
"Least number of buses" is not the same as "shortest path or least number of stops", my understanding is we are trying to find a path with least switch between buses, I wonder why BFS would work
The number of buses is just the amount of stops plus one, right?
great video!
Is there a pattern as in when to use BFS and DFS???
Typically you use BFS for when you want the shortest path, DFS for when you need to explore all paths. If the problem can be solved using either, I always prefer BFS because I find it easier to code and you don’t have to worry about overflow in extreme cases
I tried your solution but unfortunately I got a TLE. Not sure what to do about that
Hmm, did you mess up an indentation somewhere? I recall getting a TLE due to an indentation issue
@@crackfaang I have optimized it by: 1 - check if the target exists before you started BFS (case #44?), 2 - check for visited before adding anything into the queue. This fixed all TLE problems for me
Thanks