Задание №23. Короткий конспект

В варианте №23 на кратчайший путь дан ациклический ориентированный граф с положительными весами. Требуется минимальная сумма весов от старта 1 до финиша 100; в ответе — её целая часть. Наличие пути гарантировано.

Опорные обозначения

Для вершины, отличной от старта: d(v)=\min_{u\to v}\bigl(d(u)+w(u,v)\bigr). Здесь w(u,v) — вес последнего ребра. Сравниваются все входящие рёбра. Пустой набор кандидатов или только недостижимые предшественники дают \infty.

Порядок вычисления

1. Читается весь файл без пропуска первой строки: заголовка нет. line.split() разделяет поля по пробелам и табуляциям.
2. Для каждого конца ребра сохраняются пары «начало, вес». Номера преобразуются в int, вес — в Decimal непосредственно из строки.
3. Функция расстояния рекурсивно запрашивает расстояния до предшественников и берёт минимум сумм. Отдельный случай старта возвращает 0; отсутствие входящих рёбер — бесконечность.
4. @cache сохраняет результат для каждой вершины. Повторный запрос получает готовое значение. Ацикличность исключает замкнутую цепочку вызовов.
5. После нахождения d(100) целая часть вычисляется через int(d(100)). Промежуточные веса и суммы не усекаются.

Короткая проверка

Путь через два ребра весов 5{,}5 и 2 имеет длину 7{,}5, что меньше прямого перехода веса 12. Целая часть — 7. Этот результат относится к малому примеру; у полного файла свой ответ.

Возможные ловушки

• Обратное чтение ребра меняет достижимость: 6 1 1.0 разрешает только 6\to1.
• Числовая сортировка вершин не задаёт зависимости. Вычисление следует рёбрам, в том числе от большего номера к меньшему.
• Ноль вместо бесконечности создаёт несуществующий путь. Нулевое начальное расстояние есть только у старта.
• round округляет, а требуется отбросить дробную часть. Усечение отдельных весов может изменить сумму. Целая часть берётся только у итоговой минимальной длины.