e-olymp 4853. Кратчайший путь

Условие:

Задан неориентированный граф. Найдите кратчайший путь от вершины $start$ до вершины $end$.

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

В первой строке находится два целых числа $n$ и $m$ $ (1 ≤ n ≤ 50000, 1 ≤ m ≤ 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $start$ и $end$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

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

Если пути между $start$ и $end$ нет, то выведите $-1$. Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты:

Входные данные Выходные данные
1 4 5
1 4
1 3
3 2
2 4
2 1
2 3
2
1 2 4 
2
5 3
1 4
2 3
3 5
3 4
 -1
3 5 4
1 4
1 2
2 3
3 5
3 4
3
1 2 3 4

Решение:

Поскольку нам необходимо найти кратчайшее расстояние между вершинами реализуем поиском в ширину. Запомним посещенные вершины в массиве [latex]used[/latex], родительские вершины в массиве [latex]parent[/latex], а план посещений в списке [latex]plan[/latex].
Изначально в списке [latex]plan[/latex] находится единственная вершина $start$. Каждый шаг начинается с того, что мы берем первую вершину из списка [latex]plan[/latex], отмечаем ее как посещенную, удаляем из списка и после посещаем все ее соседние вершины, которые еще не были посещены.
Когда очередь опустеет, обход в ширину обойдёт все достижимые из [latex]point[/latex] вершины, причём до каждой дойдёт кратчайшим путём. После того, как кратчайший путь найден — мы с помощью массива «предков» восстанавливаем его.

 

try online