Дана таблица длин дорог между пунктами: нужно найти длину самого короткого маршрута, иногда с условием «через пункт» или «не заезжая в пункт». Часть 1, ответ — число в бланке № 1, 1 балл.
Часть
1
Ответ
число в бланке № 1
Баллы
1 балл
Проверяет
умение анализировать простую модель — таблицу дорог между пунктами
Сколько времени закладывать
около 3 минут по спецификации ФИПИ
Какие бывают подтипы
Кратчайший путь — Самый короткий маршрут между двумя пунктами; прямая дорога часто оказывается длиннее объезда.
Через указанный пункт — Маршрут обязан пройти через заданный пункт, поэтому путь делится на две части.
Минуя пункт — Один пункт запрещён — все маршруты через него отбрасываются.
Пример с полным разбором
Условие. Между пунктами A, B, C, D, E построены дороги, их длины в километрах даны в таблице; пустая клетка означает, что прямой дороги нет. Найдите длину кратчайшего пути из A в E. Каждый пункт можно посетить не больше одного раза.
A
B
C
D
E
A
7
3
12
B
7
2
4
C
3
2
8
8
D
4
8
1
E
12
8
1
Прямая дорога из A в E есть, её длина 12 — это только первый кандидат.
Из A ближе всего до C (3 км). Из C в E напрямую 8 км, вместе 3+8=11.
Из C можно свернуть в B (2 км), оттуда в D (4 км), а из D в E (1 км): 3+2+4+1=10.
Остальные маршруты длиннее: A–B–D–E и A–C–D–E дают по 12 км.
Ответ: 10
Частые ошибки
Берут прямую дорогу и не проверяют объезды.
Останавливаются на первом найденном маршруте.
Теряют условие «через пункт» или «не через пункт».
Принимают пустую клетку за дорогу длины ноль, хотя дороги там нет.
Ошибаются в сумме из трёх-четырёх чисел.
Что нужно знать для задания 4
Оглавление курса «ОГЭ по информатике» под это задание. Содержание открывается после оплаты.