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