I am interested in this problem conceptually, thus I could use an algorithm in words (not code or pseudocode). a proof of run time would also be helpful. I will give multiple thumbs up. cheers!

Problem 4: Finding a cheap flight. Let G = (V, E) be a directed graph, where V is a set of cities, and E represents all possible flights between the cities in V. For every edge {u, v} E E, you are given the duration of a direct flight from u to v, denoted by d(u, v), which is an integer. For example, if you are at city u at time t, and you take a direct flight to v, departing at time t' > t, then you arrive at v at time ' + d(u, v). For every {u, v} E E, you are given a timetable of all available direct flights from u to v, for some interval {0,...,T}, where T > 0 is an integer. That is, for any {u, v} E E, you are given a list of pairs of integers (tu,v,1,Cu,v,1),..., (tu,w.k, Cu,v,k)), where the pair (tu,v,i, Cu,v.i) denotes the fact that there is a direct flight from u to v that departs at time tuvi, and costs Cu,vi dollars. Design an algorithm that given a pair of cities u, v E V, computes the cheapest possible route that starts at u at time 0, and ends at v at time at most T. Prove that your algorithm is correct, and that its running time is polynomial in V and T. Hint: Express the above problem as shortest-path computations in some graph