- Описание
- Отправленные решения
12. Длина кратчайшего пути
Дан неориентированный граф. Найдите длину минимального пути между двумя вершинами.
Формат ввода
В первой строке записано целое число () – количество вершин в графе.
Далее записывается матрица смежности — строк, в каждой из которых содержится чисел 0 или 1, разделённых пробелом. Число 0 означает отсутствие ребра, а 1 — наличие ребра.
В последней строке задаются номера двух вершин — начальной и конечной.
Вершины нумеруются с единицы.
Формат вывода
Выведите длину кратчайшего пути — минимальное количество ребер, которые нужно пройти.
Если пути нет, нужно вывести -1.
Ограничения
Ограничение времени
1 с
Ограничение памяти
64 МБ
Пример 1
Ввод
10
0 1 0 0 0 0 0 0 0 0
1 0 0 1 1 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 1 1 0 0 0 0
5 4
Вывод
2
Пример 2
Ввод
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