ЕГЭ информатика, задание 23: №23 · Графы: пути
Дан ориентированный граф без циклов; в скобках — длины рёбер: А→В (10), Б→В (9), В→Г (2), В→Е (8), Г→Д (2), Г→Е (13), Д→Е (4), Е→Ж (2), Е→И (3), Ж→З (11), Ж→И (9), Ж→К (14), З→И (3), И→К (14). Найди наименьшую длину пути из вершины А в вершину К.
Показать ответ и разбор
Ответ: 34
Динамика по вершинам в порядке букв: лучшая длина до вершины = минимум по входящим рёбрам. Ответ: 34. Это новое задание ЕГЭ-2027: граф без циклов позволяет считать всё за один проход.
Потренируйся в боте. Такие задания с разбором, статистика по темам и работа над ошибками: бесплатно в Telegram.
Решить это задание в боте @infkostbot
Решить это задание в боте @infkostbot
Ещё задания по теме
- Дан ориентированный граф без циклов (рёбра): А→Б, А→В, Б→Г, Б→Д, В→Г, В→Д, В→Е, Г→Д, Г→Е,…
- Дан ориентированный граф без циклов (рёбра): А→Б, А→Г, Б→В, В→Д, В→Е, Г→Д, Г→Е, Д→Ж, Д→З,…
- Дан ориентированный граф без циклов (рёбра): А→Б, А→Г, Б→В, Б→Г, В→Г, В→Д, Г→Е, Г→Ж, Д→Е,…
- Дан ориентированный граф без циклов; в скобках — длины рёбер: А→Б (4), А→В (4), А→Г (3),…