The first morning after returning from a glorious spring break, Alice wakes to discover that her car won’t start, so she has to get to her classes at Sham-Poobanana University by public transit. She has a complete transit schedule for Poobanana County. The bus routes are represented in the schedule by a directed graph G, whose vertices represent bus stops and whose edges represent bus routes between those stops. For each edge u->v, the schedule records three positive real numbers:

l(u->v) is the length of the bus ride from stop u to stop v (in minutes)

f(u->v) is the first time (in minutes past 12am) that a bus leaves stop u for stop v.

∆(u->v) is the time between successive departures from stop u to stop v (in minutes).

Thus, the first bus for this route leaves u at time f(u->v) and arrives at v at time f(u->v) + l(u->v), the second bus leaves u at time f (u->v) + ∆(u->v) and arrives at v at time f (u->v) + ∆(u->v) + l(u->v), the third bus leaves u at time f (u->v) + 2 · ∆(u->v) and arrives at v at time f (u->v) + 2 · ∆(u->v) + l(u->v), and so on. Alice wants to leaves from stop s (her home) at a certain time and arrive at stop t (The See-Bull Center for Fake News Detection) as quickly as possible. If Alice arrives at a stop on one bus at the exact time that another bus is scheduled to leave, she can catch the second bus. Because she’s a student at SPU, Alice can ride the bus for free, so she doesn’t care how many times she has to change buses.

Describe and analyze an algorithm to find the earliest time Alice can reach her destination. Your input consists of the directed graph G = (V, E), the vertices s and t, the values l(e), f (e),∆(e) for each edge e ∈ E, and Alice’s starting time (in minutes past 12am).