Задание 23. ЕГЭ Инф. 2027

from functools import cache
from collections import defaultdict

# 1. Чтение графа
g = defaultdict(list)
for s in open('23.txt'):
    u, v, w = s.split()
    g[int(u)].append((int(v), float(w)))


# 2. Универсальная функция поиска (a - текущая вершина, b - конечная цель)
@cache
def f(a, b):
    # --- БЛОК ИЗБЕГАЕМЫХ ВЕРШИН ---
    # if a in (2767, 3000): 
    #     return float('inf')

    # УСПЕХ: Дошли до цели b
    if a == b:
        return 0

    # ОТБРАКОВКА: Тупик
    if not g[a]:
        return float('inf')

        # Рекурсивный переход: идем в соседнюю вершину v, конечная цель b сохраняется
    return min(w + f(v, b) for v, w in g[a])

# 3. Конструктор ответа (раскомментировать нужный вариант):

# ВАРИАНТ 1: Обычный путь (из 1 в 100)
# ans = f(1, 100)

# ВАРИАНТ 2: С обязательной вершиной (из 1 в 100 через 50)
# ans = f(1, 50) + f(50, 100)

# ВАРИАНТ 3: Комбо (две обязательные вершины 50 и 75 на пути из 1 в 100)
# ans = f(1, 50) + f(50, 75) + f(75, 100)

# ВЫВОД: отбрасываем дробную часть только у финальной суммы
# print(int(ans))