Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra's algorithm solution in Clear category for Useless Flights by David_Jones
from collections import defaultdict
from math import inf
def useless_flight(schedule):
G = defaultdict(set)
w = {}
for u, v, cost in schedule:
G[u].add(v)
G[v].add(u)
w[u,v] = w[v,u] = cost
indices = []
for i, (a, b, _) in enumerate(schedule):
d = {u : inf for u in G}
d[a] = 0
while d:
u = min(d, key=d.get)
if u == b:
if d[u] < w[a,b]:
indices.append(i)
break
for v in G[u]:
if v in d:
d[v] = min(d[v], d[u] + w[u,v])
del d[u]
return indices
June 3, 2019
