Answer Happy

Question 19 30 pts Suppose there are n airports in Europe denoted by A1, A2,..., An. The cost to take a flight from airport Aj to airport A; is C[i, j] > 0 if there is a direct flight from airport A; to airport Aj; if there is no direct flight from airport A; to airport A; then C[i, j = NULL. There are m direct flights in total. A) (10 points) Design an algorithm that runs in O(n + m) time to decide if one can fly from airport A; to airport Aj with at most k transits (or at most k + 1 flights). Note that the input in this case is the array C, a number k, and the two airports Ai, Aj. B) (10 points) Design an efficient algorithm that finds the pair of airports Ai and Aj such that flying from Aį to A; is as expensive as possible. Note that the input in this case is just the array C and you need to find the most expensive departure and destination pair. What is the running time of your algorithm? C) (10 points) Suppose the cost of a direct flight can now be negative (e.g., travel vouchers that give you money to take a flight). Give an efficient algorithm to find the cheapest possible destination if you want to fly out from a given airport Aj. Note that the input in this case is the array C and the given departure airport Ai. Edit View Insert Format Tools Table 12ptv Paragraph в І U AT?v V р O words