ЕГЭ · ЗАДАНИЕ 1
Графы и таблицы дорог · практика 15
Между пунктами есть только следующие двусторонние дороги. Найдите длину кратчайшего пути из A в E. По дороге можно проезжать промежуточные пункты.
| Дорога | Длина |
|---|---|
| A–B | 6 |
| A–C | 9 |
| B–D | 7 |
| C–D | 8 |
| D–E | 10 |
| B–E | 18 |
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 23
Решение по шагам
- Ищем именно сумму длин дорог, а не число вершин. При положительных длинах возвращение в уже посещённую вершину удлиняет путь.
- Перечислим все простые пути из A в E. Это также проверяет, что мы не пропустили обход через B.
- Выберем минимальную сумму: 23.
| Путь | Сложение | Сумма |
|---|---|---|
| A → B → E | 6 + 18 | 24 |
| A → B → D → E | 6 + 7 + 10 | 23 |
| A → C → D → E | 9 + 8 + 10 | 27 |
| A → C → D → B → E | 9 + 8 + 7 + 18 | 42 |