Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Useless Flights 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 min_money > 0 and money > min_money:
continue
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
def useless_flight(schedule: List) -> List:
unnecessary_flights = []
for flight_number, flight in enumerate(schedule):
#if flight[2] <= 90: continue
min_money = cheapest_flight(schedule, flight[0], flight[1])
if min_money < flight[2] and min_money != 0:
unnecessary_flights.append(flight_number)
return unnecessary_flights
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","H",35],["A","I",10],["A","J",45],["A","M",70],
["B","E",25],["B","H",45],["B","N",55],["B","O",30],["C","D",75],["C","G",85],
["C","J",45],["C","K",50],["D","G",30],["D","K",80],["D","L",85],["E","O",85],
["F","G",50],["F","J",75],["F","M",70],["F","N",45],["G","J",40],["H","M",40],
["H","O",50],["I","K",30],["I","L",90],["I","O",50],["K","L",55],["M","N",75]]) == [15, 24]
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!")
May 23, 2021