Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
6 lines, commented solution in Clear category for The Cheapest Flight by CDG.Axel
from typing import List
def cheapest_flight(costs: List, a: str, b: str) -> int:
# add back routes to costs, init shortest cost list
costs, res = costs + [[t, f, c] for f, t, c in costs], {a: 0}
# while exists any ways from shortest cost list
while any(c[0] in res for c in costs):
for r in res.copy():
# update ways form shortest const list
[res.update({t: min(res.get(t, 1e10), res[r] + c)}) for f, t, c in costs if f == r]
# and remove ways we used
costs = [c for c in costs if c[0] != r]
return res.get(b, 0)
if __name__ == '__main__':
print("Example:")
print(cheapest_flight([['A', 'C', 100],
['A', 'B', 20],
['B', 'C', 50]],
'A',
'C'))
# These "asserts" are used for self-checking and not for an auto-testing
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("Coding complete? Click 'Check' to earn cool rewards!")
Sept. 19, 2021
Comments:
