Путь в графе
В неориентированном графе требуется найти минимальный путь между двумя вершинами.
Входные данные
Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.
Выходные данные
Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.
Необходимо вывести путь (номера всех вершин в правильном порядке). Если пути нет, нужно вывести -1.
Примеры
Входные данные
5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5
Выходные данные
3 3 2 1 5
algoprog.ru © Петр Калинин, GNU AGPL, github.com/petr-kalinin/algoprog | О лицензии на материалы сайта | Блог