Условие
Длина пути
В неориентированном графе требуется найти длину минимального пути между
двумя вершинами. Гарантируется, что путь существует.
Входные данные
Во входном файле записано сначала число N - количество вершин в графе
(1<=N<=100). Затем записана матрица смежности (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
Подсказка
Рассматривается и разбирается волновой алгоритм. Он
разбирается на примере таблицы, а затем обощается на графы. На мой взгляд,
писать его на графе даже проще, чем на таблице, хотя для понимания
таблица, возможно, несколько нагляднее.
Решение
Скачать архив тестов
Источники и прецеденты использования
|
|
|
Курс |
|
предмет |
информатика |
|
Название |
Основы программирования на языке Паскаль |
|
Класс |
8 |
|
Автор |
Матюхин Виктор Александрович |
|
Место проведения |
Московская гимназия на Юго-Западе N1543 |
|
задача |
|
Номер |
160 |
