МЭШ
Цифровое Домашнее Задание
ЗАДАНИЕ 7
Введите ответ в числовое поле
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Таблица дорог:
| A | B | C | D | E | F | |
| A | 3 | 4 | 15 | |||
| B | 3 | 3 | 4 | |||
| C | 4 | 3 | 1 | 6 | ||
| D | 4 | 1 | 2 | 6 | ||
| E | 2 | 1 | ||||
| F | 15 | 6 | 6 | 1 |
Решение:
Нам нужно найти кратчайший путь из пункта A в пункт F, который НЕ проходит через пункт C.
Это означает, что мы должны исключить все пути, которые включают пункт C.
Давайте перечислим все возможные пути из A в F, избегая C, и посчитаем их длины.
Прямой путь:
- A → F: Длина = 15
Пути через B:
- A → B → D → E → F: Длина = (A-B) + (B-D) + (D-E) + (E-F) = 3 + 4 + 2 + 1 = 10
- A → B → D → F: Длина = (A-B) + (B-D) + (D-F) = 3 + 4 + 6 = 13
Пути через D (без C):
Из A в D нет прямой дороги. Нужно идти через B.
- A → B → D → E → F: (уже посчитано) = 10
- A → B → D → F: (уже посчитано) = 13
Пути через E (без C):
Из A в E нет прямой дороги. Нужно идти через D.
- A → B → D → E → F: (уже посчитано) = 10
Давайте систематизируем все возможные пути из A в F, не проходящие через C, и их длины:
1. A → F: Длина = 15
2. Пути, начинающиеся с A → B:
- A → B → D → E → F: 3 (A-B) + 4 (B-D) + 2 (D-E) + 1 (E-F) = 10
- A → B → D → F: 3 (A-B) + 4 (B-D) + 6 (D-F) = 13
3. Пути, начинающиеся с A → D: (Нет прямой дороги A-D)
4. Пути, начинающиеся с A → E: (Нет прямой дороги A-E)
Теперь сравним все найденные длины путей:
- 15 (A → F)
- 10 (A → B → D → E → F)
- 13 (A → B → D → F)
Наименьшая из этих длин - 10.
Ответ:
10