Компания выбирает самый дешёвый способ довезти груз от склада до магазина.
Реши задание на изображении
Сверь числа и знаки с фото.
Самый дешёвый маршрут Компания выбирает самый дешёвый способ довезти груз от склада до магазина.
Число у дуги — стоимость проезда в рублях. Двигаться можно только по стрелке.
[Рисунок: ориентированный граф. Слева вершина А. Из неё дуги: А → Б (2) вверх и А → В (7) вправо. Из Б: Б → Г (9) вправо и Б → В (3) вниз-вправо. Из В: В → Г (1) вверх-вправо и В → Д (8) вниз-вправо. Из Г: Г → Е (4) вниз-вправо. Из Д: Д → Е (2) вверх-вправо. Вершина Е справа.]
Определи стоимость самого дешёвого маршрута из А в Е. Введи одно целое число.
Краткий ответ: 10.
Стоимость маршрута — это сумма чисел на пройденных стрелках. Для каждой вершины запоминаем только самую дешёвую стоимость, потому что более дорогой путь в ту же вершину дальше уже не сможет стать лучше.
- Б: \(2\)
- В: \(\min(7,\; 2+3)=5\) — дешевле через Б
- Г: \(\min(2+9,\; 5+1)=6\) — дешевле через В
- Д: \(5+8=13\)
- Е: \(\min(6+4,\; 13+2)=10\)
Лучший маршрут: А → Б → В → Г → Е, его стоимость:
\[ 2+3+1+4=10 \]
Проверка остальных вариантов:
А → В → Г → Е: \(12\);
А → Б → Г → Е: \(15\);
А → Б → В → Д → Е: \(15\);
А → В → Д → Е: \(17\).
Все они дороже, поэтому в ответ нужно ввести 10.
