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

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

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

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

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

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

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