Задание 4 ОГЭ: кратчайший путь через пункт
Кратчайший путь через заданный пункт. Тема номера — кратчайший путь по таблице. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.
Пример
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 7 | 1 | ||||
| B | 6 | 4 | 3 | |||
| C | 7 | 9 | 3 | |||
| D | 1 | 6 | 9 | 6 | ||
| E | 4 | 3 | ||||
| F | 3 | 6 |
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Ответ
17Решение
Строим дерево путей из A: из каждого пункта — все дороги, кроме тех, что ведут туда, где уже были. Дерево строится как обычно, но в ответ берём только ветки, в которых встретился пункт C.
Пути через C (от коротких к длинным):
A–C–E–B–F: 7 + 3 + 4 + 3 = 17
A–D–C–E–B–F: 1 + 9 + 3 + 4 + 3 = 20
A–C–D–F: 7 + 9 + 6 = 22
A–C–D–B–F: 7 + 9 + 6 + 3 = 25
Без условия ответ был бы 7 по пути A–D–F, но он не заходит в C.
Ответ: 17.