Форум » Поиск путей в графе » Задача ОГЭ 1192 Поиск пути у графе » Ответить
Задача ОГЭ 1192 Поиск пути у графе
Inna: В задаче ОГЭ №1192 найти путь, соответствующий ответу, не удаётся. Задание КИМ № 4: ОГЭ: Анализ моделей объектов Раздел № 127: ОГЭ: Кратчайший путь в графе с ограничениями (О. Щецова) Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами A и B, проходящего через пункт D. Передвигаться можно только по указанным дорогам. Мое решение: A-F-E-D-С-B=5+2+3+3+4=17. Ответ должен быть 16. Где ошибка?
Ответов - 6
Поляков: Можно проходить дважды через один и тот же пункт.
Inna: Константин Юрьевич, не пойму, через какой пункт можно пройти дважды, чтобы получилось 16?
Поляков: Попробуйте независимо найти оптимальные маршруты A->D и D->B, а потом их соединить.
Бакалов: В задаче ОГЭ №1192 Поляков пишет: Попробуйте независимо найти оптимальные маршруты A->D и D->B, а потом их соединить. Константин Юрьевич, получается, что мы проходим через пункт в который мы должны прийти в финале, таким образом мы получается попали в пункт B не пройдя через D A-F-E-D-С-B=5+2+3+3+4=17.
Inna: Спасибо, нашла. Получается, что путь проходит по одни и тем же ребрам дважды. А учим детей, что так быть не должно:-(
Фёдор: A->B->C->D->C->B = 16 2+3+4+3+4=16
полная версия страницы