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

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

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

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

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

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

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