ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64182
Тема:    [ Кратчайшие пути в графах ]
Сложность: 2
Классы: 8
В корзину
Прислать комментарий

Условие

Длина пути

В неориентированном графе требуется найти длину минимального пути между
двумя вершинами. Гарантируется, что путь существует.

Входные данные
Во входном файле записано сначала число 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .