Q$3$: You are traveling by car from one city to another city. Unfortunately, you have a hole in your gas tank,

and you have to refill your gas tank to travel across more than two roads. In addition, there is a toll booth

on every road that charges you for using that road. Your goal is to find the least expensive path from your

start to your destination. You represent the city network using a directed graph $G=(V,E,w)$ with weights

$w$ defined on both edges and vertices. The vertices $V$ represent the cities and the edges $E$ represent the

roads. The weight w$($e$)$ of an edge e represents the toll amount on that road. The weight $w(v)$ of a vertex

$v$ is the price of filling your gas tank in that city $($which is a fixed price independent of how much gas you

have left, or $$ if there is no gas available to purchase$).$ You are allowed $($but not obligated$)$ to end your

journey with an empty tank, and you may assume that you always start your journey with a full tank.

Below is an example graph that we will use to answer part $($a$).$ One seemingly cheap path from $s$ to $t$ is $(s,$

$u1,u2,t)$ at a cost of $$8.$ Unfortunately, this path is not valid, because our leaky gas tank won't permit

moving across three edges without refilling our gas tank. One valid path is $(s,u3,u2,t)$ at a cost of $$22.$

$($This is a valid path: we begin with a full tank, travel across one edge to a gas station where we refill our

tank$,$ and then travel two edges to the destination, arriving with an empty gas tank. Notice that we are

unable to continue the journey to $45$ if we wanted to because even though there is a gas station there,

we have to traverse a third edge to get to it$.)$