| 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 |
- from typing import List
- def useless_flight(schedule: List) -> List:
- result = []
- nodes = [s for s, d, _ in schedule] + [d for s, d, _ in schedule]
- for i, e in enumerate(schedule):
- x, y, p = e
- graph = sorted([z for z in schedule if z != e], key=lambda x: x[2])
- if nodes.count(x) > 1 and nodes.count(y) > 1 and route_price(graph, x, y, [], p) < p:
- result.append(i)
- return result
- def route_price(graph, source, dest, visited, best=100000, price=0):
- if source == dest:
- return price
- for s, d, p in graph:
- if d == source:
- s, d = d, s
- if s == source and d not in visited and price + p < best:
- p_new = route_price(graph, d, dest, visited + [s], best, price + p)
- best = min(best, p_new)
- return best
- 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]
- assert useless_flight([["A", "E", 45], ["A", "H", 85], ["A", "K", 60], ["A", "N", 20], ["B", "C", 90],
- ["B", "Q", 70], ["B", "X", 60], ["B", "Y", 100], ["C", "R", 55], ["C", "X", 30],
- ["D", "F", 10], ["D", "T", 50], ["D", "U", 75], ["D", "V", 35], ["E", "H", 55],
- ["E", "J", 40], ["E", "M", 35], ["F", "J", 95], ["F", "M", 10], ["G", "N", 75],
- ["G", "P", 75], ["G", "W", 40], ["H", "V", 15], ["I", "O", 10], ["I", "Q", 10],
- ["I", "S", 70], ["J", "M", 80], ["J", "V", 20], ["K", "U", 85], ["K", "V", 80],
- ["K", "Y", 35], ["L", "P", 15], ["L", "R", 40], ["L", "X", 50], ["N", "P", 70],
- ["N", "W", 30], ["O", "Q", 40], ["O", "S", 55], ["O", "U", 45], ["P", "W", 90],
- ["Q", "Y", 10], ["R", "X", 95], ["S", "T", 100], ["T", "U", 30], ["W", "Y", 15]]) == [7, 17, 19, 25, 26, 36, 41]
|
