4
Шешімі: Кратчайший путь через пункт E
ОГЭ · Информатика · Тапсырма 4 · Графы и пути
КүрделіФИПИDDD73BҚысқа жауап≈ 3 минутТалдау 3 қадамЖауап сверен с ключом
Условие
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами A и D, проходящего через пункт E, при условии, что передвигаться можно только по указанным в таблице дорогам. Каждый пункт можно посетить только один раз.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 5 | 6 | 10 | 5 | |
| B | 5 | 4 | |||
| C | 6 | 2 | 7 | ||
| D | 10 | 4 | 2 | 5 | |
| E | 5 | 7 | 5 |
Таблица 1 · протяжённость дорог между населёнными пунктами
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешім по шагам
3 қадам1
Рассмотрим путь A–E–D, который проходит через E и не повторяет пункты.
$$A\text{–}E\text{–}D$$2
Его длина равна сумме длин дорог A–E и E–D.
$$5 + 5 = 10$$Другие простые пути через E имеют большую длину, например A–C–E–D: $6 + 7 + 5 = 18$.
$$6 + 7 + 5 = 18$$Жауап
10
10
так ответ выглядит в бланкеГде здесь ошибаются
Не учитывают обязательное прохождение через пункт E.
Складывают длины дорог, не проверяя, что каждый пункт можно посетить только один раз.
Выбирают прямой путь A–D длиной 10, который не проходит через E.