Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Useless Flights by Guest_5a80b5eb
from heapq import heappush, heappop
from math import inf
#re-used function from "cheapest flight" mission
def cheapest_flight(route_table, a, b):
route = {a: (0, None)}
options = []
heappush(options, (0, a))
while options:
current = heappop(options)[1]
if current == b:
break
for leg in route_table:
if current in leg:
#extract next city info
leg = leg.copy()
leg.remove(current)
next_cost = route[current][0] + leg[1]
next_city = leg[0]
if next_city not in route or next_cost < route[next_city][0]:
route[next_city] = next_cost, current
heappush(options, (next_cost, next_city))
try:
return route[b][0]
except KeyError:
return inf
def useless_flight(route_table):
useless = []
for (index, (a, b, cost)) in enumerate(route_table):
if cost > cheapest_flight(route_table, a, b):
useless.append(index)
return useless
if __name__ == '__main__':
print("Example:")
print(useless_flight([['A', 'B', 50],
['B', 'C', 40],
['A', 'C', 100]]))
# These "asserts" are used for self-checking and not for an auto-testing
assert useless_flight([['A', 'B', 50],
['B', 'C', 40],
['A', 'C', 100]]) == [2]
assert useless_flight([['A', 'B', 50],
['B', 'C', 40],
['A', 'C', 90]]) == []
assert useless_flight([['A', 'B', 50],
['B', 'C', 40],
['A', 'C', 40]]) == []
assert useless_flight([['A', 'C', 10],
['C', 'B', 10],
['C', 'E', 10],
['C', 'D', 10],
['B', 'E', 25],
['A', 'D', 20],
['D', 'F', 50],
['E', 'F', 90]]) == [4, 7]
print("Coding complete? Click 'Check' to earn cool rewards!")
March 29, 2022
