1
Ответ: Кратчайший путь в графе
ЕГЭ · Информатика · Задание 1 · Графы и пути
ПовышеннаяФИПИ5AeA27Выбор варианта≈ 3 минутыОтвет сверен с ключом
Правильный ответ
2
2
так ответ выглядит в бланкеЭто официальный ключ к заданию, источник — открытый банк заданий ФИПИ. Свой ответ можно сверить на странице задачи.
В бланк: номер выбранного варианта.
Условие
Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и G при условии, что передвигаться можно только по построенным дорогам.
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | — | 4 | 8 | 4 | 18 | ||
| B | 4 | — | 4 | ||||
| C | 8 | 4 | — | 3 | 3 | ||
| D | 4 | 3 | — | ||||
| E | 3 | — | 4 | 7 | |||
| F | 4 | — | 2 | ||||
| G | 18 | 7 | 2 | — |
Таблица протяжённости дорог между населёнными пунктами
Где здесь ошибаются
Выбрать прямую дорогу A–G длиной 18, не проверив составные маршруты.
Сложить длины дорог несуществующего маршрута.
Пропустить одну из дорог при подсчёте длины маршрута.