3. Finding a cheap flight Imagine you graduated and got a job at stingyflights.com. Your task is to design an algorithm for finding cheap flights. You are given a list of n cities, and a list of m flights between them. For each flight i, you are given its departure city Xi, its destination city yi, its departure time ti, its duration di, and its cost ci. So flight i departs from city ri at time t,, arrives at city y, at time ti+di, and costs ci dollars Design an algorithm that given a pair of cities a, b, computes the cheapest possible route (i.e. sequence of flights) that starts at a at time 0, and ends at b at time at most T The running time of your algorithm should be polynomial in n and m (e.g. O(n10m5 Hint: Express the above problem as shortest-path computation in some graph. 3. Finding a cheap flight Imagine you graduated and got a job at stingyflights.com. Your task is to design an algorithm for finding cheap flights. You are given a list of n cities, and a list of m flights between them. For each flight i, you are given its departure city Xi, its destination city yi, its departure time ti, its duration di, and its cost ci. So flight i departs from city ri at time t,, arrives at city y, at time ti+di, and costs ci dollars Design an algorithm that given a pair of cities a, b, computes the cheapest possible route (i.e. sequence of flights) that starts at a at time 0, and ends at b at time at most T The running time of your algorithm should be polynomial in n and m (e.g. O(n10m5 Hint: Express the above problem as shortest-path computation in some graph