Answer 10 BFS

mail@pastecode.io avatar
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))