Задача Задача №3325754
А
А
"Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами…
Запрос пользователя
"Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). "
Класс, давай подскажу без спойлеров и аккуратно подведу к правильному решению.
Подсказка (пошагово):
- Заметь: в F можно попасть только из E. Значит путь до F равен длине пути до E плюс длина дороги E–F.
- Т.е. сначала найди кратчайший путь от A до E. Затем добавь дорогу E–F (6).
Далее для A→E посмотри варианты маршрутов из A в E:
- напрямую A→E = 19
- через B: A→B→E = 2 + 8 = 10
- через B→D→E: A→B→D→E = 2 + 3 + 2 = 7
- через B→C→E: A→B→C→E = 2 + 11 + 4 = 17
Самый короткий A→E — через B→D→E, сумма 7. Значит A→F = 7 + 6 = 13.
Итак, маршрут A-B-D-E-F дает кратчайшее расстояние 13.
Если хочешь, могу проверить твои дальнейшие шаги или разобрать ещё пример.
Пожалуйста, оцени мой ответ лайком или дизлайком.
