Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Useless Flights by PythonLearner
from itertools import chain, product
INFINITY = float("inf")
Flight = list[str, str, int | float]
Graph = dict[str, dict[str, int | float]]
def build_graph(flights: list[Flight]) -> Graph:
cities = set(chain.from_iterable(flight[:2] for flight in flights))
graph = {city_1: {city_2: INFINITY for city_2 in cities} for city_1 in cities}
for city_1, city_2, cost in flights:
graph[city_1][city_2] = cost
graph[city_2][city_1] = cost
return graph
def floyd_warshall(weights: Graph) -> Graph:
for k, i, j in product(weights, weights, weights):
weights[i][j] = min(weights[i][j], weights[i][k] + weights[k][j])
return weights
def useless_flight(schedule: list[Flight]) -> list[int]:
shortest_paths = floyd_warshall(build_graph(schedule))
return [i for i, (city_1, city_2, cost) in enumerate(schedule) if shortest_paths[city_1][city_2] < cost]
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!")
Nov. 10, 2021
