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 tokiojapan55
from typing import List
def cheapest_flight(costs: List, a: str, b: str) -> int:
price_list = {i:({data[0],data[1]},data[2]) for i,data in enumerate(costs)}
result,stack = 0,list()
for n in price_list:
if price_list[n][0] >= {a}:
stack.append((n,))
walked = [(n,)]
if not stack:
return None
walked = [stack[0]]
while stack:
path = stack.pop(0)
t = (price_list[path[0]][0] - {a}).pop()
for p in list(path)[1:]:
t = (price_list[p][0] - {t}).pop()
if t == b:
cost = sum([price_list[p][1] for p in path])
if result == 0 or result > cost:
result = cost
for n in price_list:
if n not in path and price_list[n][0] >= {t}:
new_path = path + (n,)
if new_path not in walked:
stack.append(new_path)
walked.append(new_path)
return result
June 12, 2020
