We are given a Graph G where, s ∈ V and t ∈ V. w:E such that w represents the time from u to v. We have to calculate shortest path between s to t with a twist. The twist is the turbocharger which can be activated at any node u, such that time between u to v becomes (u,v)/3. The turbocharger has to be used just once. Find the minimum distance path between s to t.
My approach - Use BFS to calculate all the paths. When we find all the paths from s to t, apply brute force to each edge (u,v) and check the minimum result. This approach takes O(V+E) + O(E) time roughly. (I assume).
I am looking for suggestions and better approach to this problem. Please appreciate my learning phase and help me to do better at algorithms.