Каталог: Задание №23. Графы и алгоритмы
Спецификация и суть задания №23
Чтение описания ориентированного взвешенного графа из текстового файла (например, 23-1.txt), поиск кратчайшего пути с ограничением на максимальное число рёбер и вычисление суммы номеров промежуточных вершин или длины пути.
Основные прототипы и разновидности
Поиск пути из вершины A в B, содержащего не более K рёбер, минимизируя суммарный вес.
Восстановление пути и подсчёт суммы вершин вдоль оптимального маршрута.
Вычисление точного веса с дробными весами рёбер и округление вниз (int).
Теоретический фундамент и алгоритмы
1. Структура входного файла (23-1.txt):
Каждая строка файла содержит L M W, где $L$ и $M$ — вершины, $W$ — вес ребра из $L$ в $M$.
graph = {}
with open('23-1.txt') as f:
for line in f:
parts = line.split()
if not parts: continue
u, v, w = int(parts[0]), int(parts[1]), float(parts[2])
graph.setdefault(u, []).append((v, w))2. Поиск кратчайшего пути с ограничением на количество рёбер:
Используем алгоритм Дейкстры с сохранением состояния (вершина, число рёбер):
Лайфхаки и фишки для ускорения
При чтении чисел используйте parts = line.split(), так как разделителем могут быть пробелы и табуляции.
Вес W может быть вещественным (float), поэтому преобразуйте веса через float(parts[2]).
Частые ошибки и экзаменационные ловушки
Обычный Дейкстра найдёт глобально кратчайший путь, но в нём может оказаться больше допустимого числа рёбер!
Если граф содержит циклы с нулевым или малым весом, поиск в глубину без мемоизации зациклится.
Практические задачи из банка КИМ (Всего: 8)
Решать в песочнице СмартКИМВ текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вер...
В текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вер...
В текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вер...
В текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вер...
В текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вер...
В текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вер...
В текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вер...
(Демо-2027) В текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M ...
Готовьтесь к ЕГЭ эффективно со СмартКИМ
Составляйте индивидуальные пробники, решайте задачи в онлайн-песочнице со встроенным компилятором Python и Web-Excel, отслеживайте статистику и делитесь результатами с учителем.
Собрать вариант КИМ