Problem $2.$ Highway Driving $(26$ points$)$

You are given a set of cities, along with the pattern of highways between them, in the form

of an undirected and connected graph $G=(V,E).$ Each stretch of highway einE connects

two of the cities, and you know its length in miles, length $(e).$ You want to get from city $s$

to city $t.$ There is one problem: your car can only hold enough gas to drive $L$ miles. There

are gas stations in each city, but not between cities. Therefore, you can only take a route if

every one of its edges has length length $(e)L.$

$($a$)(8$ points$)$ Given the limitation on your car's fuel tank capacity, show how to determine

in linear time whether there is a feasible route from $s$ to $t.$

$($b$)(6$ points$)$ You are now planning to buy a new car, and you want to know the minimum

fuel tank capacity $C$ that is needed to travel from $s$ to $t.$ Give an $O(mlogn)$ time

algorithm to determine this.

$($c$)(12$ points$)$ Instead you upgraded and bought a car with an unlimited fuel tank capacity,

however, now you don't have much money left, and so you need to get from $s$ to $t$ as

cheaply as possible. Unfortunately, not only do you have to pay for gas, but cities have

instituted a new tax for any car that enters. Specifically, let tax$(v)$ be the tax charged to

enter city vinV. For simplicity, you can assume the cost of the gas consumed to travel

on highway einE is exactly length $(e).$ Give an $O(mlogn)$ time algorithm to find the

cheapest route from $s$ to $t($i$.$e$.$ the route minimizing the sum paid for gas and taxes$).$