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 book1978
def cheapest_flight(costs, a, b):
def make_dict_better(x, y, z):
if x in flights:
flights[x][0].append(y)
flights[x][1].append(z)
else:
flights[x] = [[y], [z], float("inf")]
flights = dict()
for x, y, z in costs:
make_dict_better(x, y, z)
make_dict_better(y, x, z)
dont_step = []
flights[a][2] = 0
do_step = [a]
print(f'{flights=}')
while do_step:
g = []
for ds in do_step:
dont_step.append(ds)
temp_dict = dict()
for ind, i in enumerate(flights[ds][0]): # D / A C
path = flights[ds][2] + flights[ds][1][ind]
if path < flights[i][2]:
flights[i][2] = path
temp_dict[i] = flights[i][2]
g += sorted(temp_dict, key=temp_dict.get)
do_step = []
for i in g:
if i not in do_step and i not in dont_step:
do_step.append(i)
return 0 if flights[b][2] == float("inf") else flights[b][2]
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 3, 2023
