Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
scipy.sparse.csgraph solution in Clear category for Useless Flights by flpo
from typing import List
from scipy.sparse import csr_matrix, dok_matrix
from scipy.sparse.csgraph import shortest_path
def useless_flight(schedule: List) -> List:
cities = list(set.union(*[set(pair) for *pair, _ in schedule]))
indexes = {city: i for i, city in enumerate(cities)}
m = dok_matrix((len(cities), len(cities)))
for s, d, cost in schedule:
m[indexes[s], indexes[d]] = cost
distances = shortest_path(csr_matrix(m), directed=False)
def useless(src, dest, cost):
return distances[indexes[src], indexes[dest]] < cost
return [i for i, fligth in enumerate(schedule) if useless(*fligth)]
May 4, 2019
Comments: