Problem $2$

Suppose you are given a directed graph $G=(V,E)$ where the vertices model cities and the edges model

flights between cities. Each edge $e$ has a weight $t(e)$ associated with it$,$ where $t(e)$ is the time taken by the

flight. Each of these times is a multiple of $15$ minutes, and on every edge there is a flight leaving every $15$

minutes $($starting at $12$:$00).$ Our friend Zimdor wishes to travel from a start city $($vertex$)v_s$ in this network

to a $($different$)$ end city $v_t.$ He wants to leave $v_s$ at $12$:$00$ and arrive at his destination $v_t$ exactly on some

hour $($for example at $4$:$00$ or $5$:$00$ or $6$:$00,$ etc. but not at $4$:$15$ or $5$:$30$ or $6$:$45).$ At any city along his route

where he changes planes, it takes $15$ minutes. For example, if he arrives at $v_a$ at $1$:$15,$ then at $1$:$30$ he will

board his next flight. He will not choose to take a longer $($or shorter$)$ layover; he must leave an intermediate

city exactly $15$ minutes after he arrives. He may visit an intermediate city $($including $v_s$ and $v_t)$ any number

of times. Find an algorithm that, given the directed graph $G,$ the weight function $t(*),$ and the start and end

cities $v_s$ and $v_t,$ finds the minimum$-$time route from $v_s$ to $v_t$ that obeys Zimdor's time constraints.