2 Краткая информация о задании 23
Краткая информация о задании 23
Задание 23 — про кратчайший путь в графе. В текстовом файле описан ациклический ориентированный взвешенный граф: каждая строка — это ребро «из вершины L в вершину M весом W». Нужно найти целую часть длины кратчайшего пути из вершины 1 в вершину 100. Существование хотя бы одного пути гарантируется.
Вершин и рёбер немного (рёбер не больше 200), но перебирать пути руками не нужно — короткий алгоритм находит кратчайшее расстояние сразу до всех вершин.
Проверяемые требования
Умение читать описание графа и находить кратчайший путь; работа с взвешенным ориентированным графом.
Уровень сложности: повышенный.
Примерное время выполнения: 6 минут.
💡 Важный момент про способ решения Задание 23 — питоновское. Достаточно прочитать рёбра из файла и прогнать один из двух алгоритмов: Беллмана–Форда (много раз улучшаем расстояния) или рекурсию с запоминанием (длину пути считаем от конца назад). Оба не требуют сортировать рёбра или строить граф вручную. Несколько строк — и ответ готов. |