Consider the stopping for gas problem we discussed in class: you are going to drive a car from New York to Las Vegas. Your cars gas tank can hold k gallons of gas, and when it is full, it holds enough gas to travel n miles. (You may assume that the mileage of your car is a constant, i.e., n/k miles/gallon.) You are given a map with distances between gas stations on your route. You wish to make as few gas stops as possible along the way. (a) Show that this problem can be solved by formulating a shortest path problem. (b) You are now concerned about the cost of gas than about the number of times you will have to spend pumping it. You still have a map giving the distances between all gas stations, and this time you also know the gas price (per gallon) at each station. You do not care how many times you have to stop, and at each stop, you will only buy enough gas to get you to the next place you plan to stop. Give an algorithm to determine where to stop for gas to minimize the total amount you spend.