# Answer 10 BFS

unknown

python

7 months ago

1.3 kB

1

Indexable

Never

^{}

from queue import Queue from collections import defaultdict def min_flights(N, a, b): graph = defaultdict(lambda: []) # graph creation as an adjacency list for i in range(1, N+1): # vertices go from 1 to n inclusive, one for each city if 2*i <= N: # adding a directed edge from i to 2*i if it exists graph[i].append(2*i) if i-1 >= 0: # adding a directed edge from i to i-1 if it exists graph[i].append(i-1) queue = Queue() # creating a queue for the bfs process and adding start vertex a to it queue.put((a, 0)) visited = {a} # creating a visited set to avoid traversing the same vertex twice while not queue.empty(): # we use bfs because it guarantees using as less as flights as possible u, level = queue.get() # we extract a vertex and its level, how many flights we did from a to reach it if u == b: # if we arrived at the destination b, we return its level, the number of flights we did return level for v in graph[u]: # traversing unvisited neighbors of the current vertex if v not in visited: visited.add(v) queue.put((v, level+1)) return -1 # no way to go from a to b, return -1 N, a, b = 10, 3, 9 print(min_flights(N, a, b))