2 Краткая информация о задании 23

Краткая информация о задании 23

Задание 23 — про кратчайший путь в графе. В текстовом файле описан ациклический ориентированный взвешенный граф: каждая строка — это ребро «из вершины L в вершину M весом W». Нужно найти целую часть длины кратчайшего пути из вершины 1 в вершину 100. Существование хотя бы одного пути гарантируется.

Вершин и рёбер немного (рёбер не больше 200), но перебирать пути руками не нужно — короткий алгоритм находит кратчайшее расстояние сразу до всех вершин.

Проверяемые требования

Умение читать описание графа и находить кратчайший путь; работа с взвешенным ориентированным графом.

Уровень сложности: повышенный.

Примерное время выполнения: 6 минут.

💡 Важный момент про способ решения

Задание 23 — питоновское. Достаточно прочитать рёбра из файла и прогнать один из двух алгоритмов: Беллмана–Форда (много раз улучшаем расстояния) или рекурсию с запоминанием (длину пути считаем от конца назад). Оба не требуют сортировать рёбра или строить граф вручную. Несколько строк — и ответ готов.

Краткая информация о задании 23 — Задание 23 ЕГЭ 2027 | Методички — Профиматика