3. You are given a graph G-(V, E) and you want to drive from a location s to another location t without running out of gas while spending as little money as possible. You are given a map of the road system designated by a set of vertices and a set of directed roads (one way) where (u, uje E means that there is a road from vertex u to vertex u. w(u, u) s the length of the road from u to , and it uses up w(u, v) gas units. You also know that some vertices S C V have gas stations. When you get to a vertex with a gas station, you can either pay c(u) dollars tol up your tank, or not get gas. (Note that the cost does not depend on the amount of gas you get, only on the gas station location. So you may as well fill up your tank if you are getting any gas.) Assume that you start with a full tank with k units of gas. Give an efficient algorithm to find the cheapest route from s to t such that you are never stranded without gas. (It is ok to run out of gas at the same moment you reach a gas station.) Analyze the running time of your algorithm. Your analysis should be in terms of S, V and E 3. You are given a graph G-(V, E) and you want to drive from a location s to another location t without running out of gas while spending as little money as possible. You are given a map of the road system designated by a set of vertices and a set of directed roads (one way) where (u, uje E means that there is a road from vertex u to vertex u. w(u, u) s the length of the road from u to , and it uses up w(u, v) gas units. You also know that some vertices S C V have gas stations. When you get to a vertex with a gas station, you can either pay c(u) dollars tol up your tank, or not get gas. (Note that the cost does not depend on the amount of gas you get, only on the gas station location. So you may as well fill up your tank if you are getting any gas.) Assume that you start with a full tank with k units of gas. Give an efficient algorithm to find the cheapest route from s to t such that you are never stranded without gas. (It is ok to run out of gas at the same moment you reach a gas station.) Analyze the running time of your algorithm. Your analysis should be in terms of S, V and E