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 brownie57
from typing import List
from collections import deque
def cheapest_flight(costs: List, a: str, b: str) -> int:
list_flight_cost = []
queue = deque([])
queue.append((a, 0))
while queue:
flight, cost = queue.pop()
for i in costs:
if flight[-1] not in i:
continue
dep = flight[-1]
ari = i[1] if dep == i[0] else i[0]
if ari in flight:
continue
if ari == b:
list_flight_cost.append(cost + i[2])
else:
queue.append((flight + ari, cost + i[2]))
if list_flight_cost:
return min(list_flight_cost)
else:
return 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!")
July 3, 2019
Comments:
