Главная › Информатика › №23 · Графы: пути

ЕГЭ информатика, задание 23: №23 · Графы: пути

Дан ориентированный граф без циклов; в скобках — длины рёбер: А→Б (7), Б→В (14), Б→Д (4), В→Г (3), Г→Д (12), Д→Ж (6), Е→Ж (10), Ж→З (14), Ж→И (10), З→К (9), З→Л (2), И→К (5), К→Л (5), К→М (3), Л→М (12). Найди наибольшую длину пути из вершины А в вершину М.

Показать ответ и разбор
Ответ: 82

Динамика по вершинам в порядке букв: лучшая длина до вершины = максимум по входящим рёбрам. Ответ: 82. Это новое задание ЕГЭ-2027: граф без циклов позволяет считать всё за один проход.

Потренируйся в боте. Такие задания с разбором, статистика по темам и работа над ошибками: бесплатно в Telegram.
Решить это задание в боте @infkostbot

Ещё задания по теме