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 oleg.sidorov.ds
def cheapest_flight(costs: list, a: str, b: str) -> int:
flights = dict()
for cost in costs:
if cost[0] not in flights:
flights[cost[0]] = {cost[1]: cost[2]}
else:
flights[cost[0]].update({cost[1]: cost[2]})
if cost[1] not in flights:
flights[cost[1]] = {cost[0]: cost[2]}
else:
flights[cost[1]].update({cost[0]: cost[2]})
prices = {a: 0}
def rec(dep, current_price):
nonlocal flights, prices
for arr, price in flights[dep].items():
if arr not in prices or current_price + price < prices[arr]:
prices[arr] = current_price + price
rec(arr, prices[arr])
rec(a, 0)
return prices.get(b, 0)
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!")
Nov. 13, 2023
