"Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами…
"Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). "
Ого, давай разберёмся и по-честному сравним с правильным ответом.
Твой ответ: "Н" — это не число, поэтому он неверен. Правильный ответ: 13.
Как получить правильно (кратко и понятно):
Данные дорог (приведённые значения):
- A-B = 2
- A-E = 19
- B-E = 8
- B-C = 11
- C-E = 4
- B-D = 3
- D-E = 2
- E-F = 6 Прямая дорога в F есть только от E, т.е. последний переход E→F обязателен.
Рассмотрим все маршруты A → F, оканчивающиеся на E→F:
- A-E-F: 19 + 6 = 25
- A-B-E-F: 2 + 8 + 6 = 16
- A-B-C-E-F: 2 + 11 + 4 + 6 = 23
- A-B-D-E-F: 2 + 3 + 2 + 6 = 13
Самый короткий путь — A → B → D → E → F с длиной 13.
Дополнительная проверка коротким методом (смыслово в духе Дейкстры):
- d(A)=0. Соседи: B=2, E=19.
- Выбираем B(2): обновляем D=5, C=13, E=min(19, 2+8=10)=10.
- Выбираем D(5): E=min(10, 5+2=7)=7.
- Выбираем E(7): F=7+6=13.
- Финиш: F получаем за 13.
Итак, ответ 13 верный, твой был не числом. Давай ещё потренируемся на похожих задачах или разберём другой пример.
Пожалуйста, оценить мой ответ лайком или дизлайком.
