# 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.
• Is it possible to do better than $O(|V|+|E|)$ time? Can you prove it? – D.W. Dec 7 '20 at 0:00
• finding all the paths take O(V+E) time as we have to apply BFS with certain restrictions i.e not to mark a node visited until there is no other path. Then, assigning the conditions of turbo charger may take extra O(E) time. There is no other way to do this from my point of view. – anony_std Dec 7 '20 at 1:59
• There can be exponentially many paths, even if $G$ is directed and acyclic: Consider a graph with $2n+2$ vertices arranged in 2 rows of $n$ vertices each, with each vertex linked to the next vertex on its right in the same row, and also to the next vertex on its right in the other row. $s$ is linked to the two leftmost vertices, and the two rightmost vertices link to $t$. There are $2^n$ $s-t$ paths, because any subset of the $n$ vertices in the top row can be visited. – j_random_hacker Dec 7 '20 at 19:15