Shortest Path with a twist 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. 
 Thank You.
First, your algorithm is not |V|+|E| because each node can be visited more than once. This is because at each stage of your BFS, there is not greedy to always visit the optimal next node. If you are generating all paths, each path visits at most all the nodes once, so the time complexity of your algorithm would actually be O(PN) where P is the total number of paths. In fact, it is likely way larger because each edge can be visited more than once.
However, there is another algorithm that can be applied to this non-negative edge-weight graph: Dijkstra's Algorithm.
To deal with the turbo charger, simply expand the graph such that each each state in your heap stores both the current weight and wether the charger has been used.