Question

пацаны, девчонки мои
Скажите ответ в данном задании, и скажите как вы его решали)

Answer 1

Во-первых, попрошу без фамильярностей в обращении. А теперь приступим к вопросу.

Перебираем все маршруты и выбираем наиболее короткий.

1. Из A мы можем попасть в B (длина 3), C (5), F (15). Выбираем короткий вариант. Идем в B.
2. Отсюда мы можем попасть только в C (1). Выбираем его.
3. Из C, если выбирать пути только вперед, мы можем попасть только в D (2). Выбираем D.
4. Из D мы можем попасть либо в E (4), либо F (6). Выбираем короткий вариант — E.
5. И из E попадаем в F по дороге длиной 1.

В итоге, длина всего пути — 3 + 1 + 2 + 4 + 1 = 11

Если бы мы выбрали в 4-м пункте сразу F, то длина была бы равна 3 + 1 + 2 + 6 = 12, что уже длиннее.

Если бы мы в первом пункте выбрали C, то длина была бы равна 5 + 2 + 4 + 1 = 12 — тоже длиннее.

Если выбрать в первом C, а потом еще и в 4-м сразу F, то длина будет равна 5 + 2 + 6 = 13 — еще длиннее.

Теперь рассмотрим самый быстрый вариант: есть маршрут напрямую из A в F, и он имеет длину 15, и является самым длинным из всех возможных маршрутов, поэтому длина кратчайшего маршрута — 11.

Ответ: 11