Статья Автор: Дубинин Дмитрий

"МЕТРО" Условие: В метро N станций. Известно, между какими станциями есть прямые перегоны. Найти минимальное количество перегонов, которое нужно проехать, чтобы попасть со станции A на станцию B.

n, m, a, b = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

dist = [-1] * (n + 1)
queue = [a]
dist[a] = 0
idx = 0

while idx < len(queue):
    v = queue[idx]
    idx += 1
    for to in graph[v]:
        if dist[to] == -1:
            dist[to] = dist[v] + 1
            queue.append(to)

print("Минимальное количество перегонов:", dist[b])

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать