1. (20 pts) You are given a directed graph G = (V, E) with positive edge weights w: V R>o. You start with a car at a specified vertex s EV and you are trying to reach the destination t EV. 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., Vor El, may lose points. Hint: you might want to define a different graph based on the input graph. (a) (3 pts) Show that the following algorithm is incorrect (i.e., find an input on which it produces a wrong answer): run Dijkstra's algorithm to find a shortest path p from s to t and then apply the turbo charge on the most expensive edge in p. breaking ties arbitrarily. (b) (7 pts) Design a correct algorithm for this problem. Describe your algorithm in plain English and briefly argue correctness. (c) (7 pts) Describe your algorithm in pseudocode. (d) (3 pts) State and justify the running time of your algorithm. It must be a function of V and E