Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for The Cheapest Flight by Kurush
from typing import List
from collections import deque
import copy
import decimal
def cheapest_flight(costs: List, a: str, b: str) -> int:
search_queue = deque()
min_money = decimal.Decimal('Infinity')
visited = set([a])
current = a
money = 0
search_queue.append([visited, current, money]);
while True:
if not search_queue: break
visited, current, money = search_queue.popleft()
if current == b:
if money < min_money: min_money = money
continue
for cost in costs:
new_visited = copy.deepcopy(visited)
if cost[0] == current and cost[1] not in visited:
new_visited.add(cost[1])
search_queue.append([new_visited, cost[1], money + cost[2]])
elif cost[1] == current and cost[0] not in visited:
new_visited.add(cost[0])
search_queue.append([new_visited, cost[0], money + cost[2]])
return min_money if min_money != decimal.Decimal('Infinity') 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!")
May 22, 2021
