Перевод (Русский)

<topic>

## Восстановление кратчайшего пути

start = int(input())                    # начальная вершина
d = [-1] * n                            # расстояние от начальной вершины
p = [-1] * n                            # родительская вершина
q = deque([start])                      # очередь вершин
d[start] = 0                            # расстояние от start до start равно 0

while q:                                # пока очередь не пуста
    v = q.popleft()                     # достаём вершину из очереди
    print(v, end=' ')                   # выводим вершину
    for to in g[v]:                     # для всех вершин, смежных с v
        if d[to] == -1:                 # если вершина ещё не посещена
            d[to] = d[v] + 1            # (start -> to) = (start -> v) + 1
            p[to] = v                   # родитель вершины to — это v
            q.append(to)                # добавляем вершину в очередь

# Восстановление пути от start до end
end = int(input())                      # конечная вершина
path = []                               # путь от start до end
while end != -1:                        # пока есть родительская вершина
    path.append(end)                    # добавляем вершину в путь
    end = p[end]                        # переходим к родительской вершине

print(*path[::-1], sep=' -> ')          # выводим путь в обратном порядке

Итак, после добавления каждой вершины в очередь мы фиксируем её родителя в массиве p и в самом конце восстанавливаем маршрут, двигаясь от конечной вершины к начальной. В итоге путь нужно вывести в обратном порядке, потому что мы начинаем восстановление с конца и переходим по родителям к началу. Чтобы пройти от start до end, нам нужно развернуть полученный список.

Рассмотрим работу алгоритма на нескольких примерах:

Обратите внимание: если в конце работы алгоритма d[end] всё ещё равно -1, это означает, что дойти до вершины end было невозможно.

Задача: Найти кратчайший маршрут

Интернет — это сеть компьютеров, соединённых друг с другом и способных передавать данные. Здесь эти компьютеры пронумерованы от 1 до n, и у нас есть информация о том, какие из них связаны напрямую. Алиса хочет отправить сообщение Бобу и желает выбрать путь, который позволит сделать это как можно быстрее. Значит, маршрут должен быть как можно короче.

Компьютеры Алисы и Боба имеют номера a и b соответственно. Требуется найти оптимальную последовательность компьютеров, по которым сообщение пройдёт от Alice к Bob за наименьшее время.

Входные данные

В первой строке содержатся два целых числа n (1 ≤ n ≤ 100 000) и e (1 ≤ e ≤ 100 000), обозначающие количество компьютеров и количество соединений в сети.

Во второй строке заданы два числа a и b (1 ≤ a, b ≤ n).

В следующих e строках содержатся пары целых чисел c1, c2 (1 ≤ c1, c2 ≤ n), указывающие, что компьютер c1 соединён с компьютером c2 и наоборот.

Выходные данные

Программа должна вывести самый короткий маршрут передачи сообщения, при этом номера компьютеров следует разделять пробелом. Если существует несколько оптимальных вариантов, можно вывести любой из них.

Примеры