Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for The Cheapest Flight by dig
from math import inf
def cheapest_flight(costs: list, a: str, b: str) -> int:
paths = [[[a, b, inf]]]
current_path = [[a, a, 0]]
def compatible(trip):
city1, city2, cost = trip
if (city1 in current_path[-1] and all(city2 not in row for row in current_path) and
all(city1 not in row for row in current_path[:-1])):
return True
elif (city2 in current_path[-1] and all(city1 not in row for row in current_path) and
all(city2 not in row for row in current_path[:-1])):
return True
return False
def backtrack():
for trip in costs:
find_path = False
if compatible(trip):
current_path.append(trip)
if b in trip:
find_path = True
paths.append(current_path.copy())
if find_path == False:
backtrack()
current_path.pop()
def price_trip(trip):
return sum(x[2] for x in trip)
backtrack()
a=price_trip(min(paths, key=price_trip))
return 0 if a == inf else a
print("Example:")
print(cheapest_flight([["A", "C", 100], ["A", "B", 20], ["B", "C", 50]], "A", "C"))
# These "asserts" are used for self-checking
assert (
cheapest_flight([["A", "C", 100], ["A", "B", 20], ["B", "C", 50]], "A", "C") == 70
)
assert (
cheapest_flight([["A", "C", 100], ["A", "B", 20], ["B", "C", 50]], "C", "A") == 70
)
assert (
cheapest_flight(
[
["A", "C", 40],
["A", "B", 20],
["A", "D", 20],
["B", "C", 50],
["D", "C", 70],
],
"D",
"C",
)
== 60
)
assert (
cheapest_flight([["A", "C", 100], ["A", "B", 20], ["D", "F", 900]], "A", "F") == 0
)
assert (
cheapest_flight(
[["A", "B", 10], ["A", "C", 15], ["B", "D", 15], ["C", "D", 10]], "A", "D"
)
== 25
)
print("The mission is done! Click 'Check Solution' to earn rewards!")
April 17, 2023
Comments:
