Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
import cheapest_flight solution in Clear category for Useless Flights by kurosawa4434
from typing import List
from collections import defaultdict
import heapq
def cheapest_flight(flight, start, goal):
flight_dic = defaultdict(lambda: defaultdict(int))
for dep, arr, cost in flight:
flight_dic[dep][arr] = cost
flight_dic[arr][dep] = cost
que = [(0, start)]
cost_dic = defaultdict(int)
done = set()
while True:
if not que:
return 0
dep = heapq.heappop(que)[1]
if dep == goal:
return cost_dic[goal]
if dep in done:
continue
for arr in flight_dic[dep]:
new_cost = flight_dic[dep][arr] + cost_dic[dep]
cost_dic[arr] = min(cost_dic[arr] or new_cost, new_cost)
heapq.heappush(que, (cost_dic[arr], arr))
done.add(dep)
def useless_flight(schedule: List) -> List:
return [i for i, (c1, c2, p) in enumerate(schedule) if p > cheapest_flight(schedule, c1, c2)]
if __name__ == '__main__':
print("Example:")
print(useless_flight([['A', 'B', 50], ['B', 'C', 40], ['A', 'C', 100]]))
# These "asserts" are used for self-checking and not for an auto-testing
assert useless_flight([['A', 'B', 50], ['B', 'C', 40], ['A', 'C', 100]]) == [2]
assert useless_flight([['A', 'B', 50], ['B', 'C', 40], ['A', 'C', 90]]) == []
assert useless_flight([['A', 'B', 50], ['B', 'C', 40], ['A', 'C', 40]]) == []
assert useless_flight([['A', 'C', 10], ['C', 'B', 10], ['C', 'E', 10], ['C', 'D', 10], ['B', 'E', 25], ['A', 'D', 20], ['D', 'F', 50], ['E', 'F', 90]]) == [4, 7]
print("Coding complete? Click 'Check' to earn cool rewards!")
Feb. 10, 2019
Comments:
