You are given a directed graph G = (V, E) with positive edge weights w : V R>0. You start with a car at a specified vertex s V and you are trying to reach the destination t V. The weight w(u, v) indicates how long it takes your car travel from vertex u to v. The goal is to compute the shortest time it takes to travel from s to t, but with a twist. The twist is that your car is equipped with a single turbo charge. You can activate the turbo charge at any node in your trip, and this has an effect of reducing the travel time along the next edge to a third of the corresponding weight. Thus, it takes w(u,v)/3 to travel from vertex u to vertex v if you decide to activate the turbo charge at the time you visit u. You can activate the turbo charge at most once during the entire trip. Design an efficient algorithm for computing the shortest time it takes you to travel from s to t. Inefficient solutions with running times with quadratic terms, e.g., or , may lose points.

Hint: you might want to define a different graph based on the input graph.

(a) Design a correct algorithm for this problem. Describe your algorithm in plain English and briefly argue correctness. (b) Describe your algorithm in pseudocode.

EL