Flights with K stops in Python

Questions 1 to 5 of 7

1. 1. Predict the output of this program. ``python import math INF = math.inf FLIGHTS = [(0, 1, 5), (1, 2, 5), (2, 4, 5), (0, 3, 2), (3, 4, 40), (0, 4, 100)] def cheapest(n, flights, src, dst, k): dist = [INF] * n dist[src] = 0 for _ in range(k + 1): nxt = dist.copy() for u, v, price in flights: if dist[u] == INF: continue candidate = dist[u] + price if candidate < nxt[v]: nxt[v] = candidate dist = nxt return -1 if dist[dst] == INF else dist[dst] for k in range(3): print(cheapest(5, FLIGHTS, 0, 4, k)) `` What does it print, one line per call, in order?

   42, then 42, then 15100, then 42, then 15100, then 60, then 30100, then 100, then 42
2. 2. Predict the output of this program, which runs with K = 0. ``python import math INF = math.inf FLIGHTS = [(0, 1, 10), (1, 2, 10), (2, 3, 10), (0, 3, 100), (0, 2, 50)] def cheapest(n, flights, src, dst, k): dist = [INF] * n dist[src] = 0 for _ in range(k + 1): for u, v, price in flights: if dist[u] == INF: continue candidate = dist[u] + price if candidate < dist[v]: dist[v] = candidate return -1 if dist[dst] == INF else dist[dst] print(cheapest(4, FLIGHTS, 0, 3, 0)) `` What does it print?

   6010030-1
3. 3. The frontier version stops as soon as the frontier is empty, even if K has not been used up. Why does this stop not change the answer?

   An empty frontier means the destination has been reached, so the search is finishedAn empty frontier means no price improved in the last level, so the next level would read the same prices and change nothingAn empty frontier means K has been used up, so no more flights are allowedAn empty frontier means every city's best price is still math.inf
4. 4. If the loop in cheapest is changed from range(k + 1) to range(k), the four-city map with K = 1 prints 100 instead of 60. Why? ``python for _ in range(k): nxt = dist.copy() for u, v, price in flights: ... ``

   One round allows only one flight, so the two-flight route 0, 2, 3 is never triedThe dist.copy() call is skipped, so the route is read from the wrong listThe destination is checked before the last round, so it still holds math.infmath.inf stops being infinite when the loop runs only once
5. 5. A map has 1000 cities and 5000 flights. With K = 2, how many flight checks does cheapest make in total, counting each flight once per round?

   Type a number.