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 tigerhu3180
from typing import List
def cheapest_flight(costs, a, b):
route = [([i], a) for i in costs if a in i]
price = 999
while route:
flight, lastPosition = route.pop(0)
st, ed, pr = flight[-1]
currentPosition = ed if st == lastPosition else st
if b in (st, ed):
price = min(price, sum([pr for _, _, pr in flight]))
else:
for nextStep in [i for i in costs if currentPosition in i and i not in flight]:
route.append((flight + [nextStep], currentPosition))
return price if price != 999 else 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!")
Feb. 1, 2019
Comments:
