A traveler has chosen to set course across America in search of some amazing driving. Assume that the roads in America can be expressed as a directed weighted graph G = (V, E, d), and that our traveler wishes to drive across at least k roads from the subset RC E of "amazing" roads. Furthermore, assume that the traveler starts and ends at her home heV. You may also assume that the traveler is fine with repeating roads from R, i.e. the k roads chosen from R need not be unique. Provide an algorithm with its proof of correctness and runtime analysis in terms of n = IV I,m = El, K, and = IRI. What is the length of the shortest path that hits at least k of these amazing roads? Hint: First consider k = 1. How can G be modified so that we can use a "common" algorithm to solve the problem? A traveler has chosen to set course across America in search of some amazing driving. Assume that the roads in America can be expressed as a directed weighted graph G = (V, E, d), and that our traveler wishes to drive across at least k roads from the subset RC E of "amazing" roads. Furthermore, assume that the traveler starts and ends at her home heV. You may also assume that the traveler is fine with repeating roads from R, i.e. the k roads chosen from R need not be unique. Provide an algorithm with its proof of correctness and runtime analysis in terms of n = IV I,m = El, K, and = IRI. What is the length of the shortest path that hits at least k of these amazing roads? Hint: First consider k = 1. How can G be modified so that we can use a "common" algorithm to solve the