Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS with defaultdict solution in Clear category for The Cheapest Flight by Sim0000
from typing import List
from collections import defaultdict, deque
def cheapest_flight(costs: List, start: str, goal: str) -> int:
d = defaultdict(dict)
for i, j, p in costs: d[i][j] = d[j][i] = p
q = deque([(start, set(), 0)])
min_cost = None
while q:
last, seen, cost = q.popleft()
if last == goal:
if min_cost is None or cost < min_cost: min_cost = cost
elif last not in seen:
seen = seen | {last} # we can not use |=
q.extend([(new_city, seen, cost + d[last][new_city]) for new_city in d[last]])
return min_cost if min_cost 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. 8, 2019