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