Условия на путь

В условии спрашивают путь не до 100, а до другой вершины — или через промежуточную. Как не переписывать функцию каждый раз?

Сделать цель вторым параметром: f(v, t) — длина кратчайшего пути из v в t. В функции меняется одна строка — сравниваем v не с 100, а с t. @cache запоминает ответ для каждой пары (v, t), так что разные цели не смешиваются.

from functools import cache graph = {}for line in open("23.txt"):    a, b, w = line.split()    a, b, w = int(a), int(b), float(w)    if a not in graph:        graph[a] = []    graph[a].append((b, w))  @cachedef f(v, t):    if v == t:        return 0    best = float("inf")    for u, w in graph.get(v, []):        best = min(best, w + f(u, t))    return best  print(f(1, 100), f(1, 4), f(6, 12))

Из 6 в 12 лучший путь — 6 → 1 → 7 → 100 → 12: 1.0 + 5.5 + 2.0 + 1.0 = 9.5. Дальше в подтеме все условия собираем из таких кусков.

Путь из 1 в 100 должен пройти через вершину 4. Как найти самый короткий такой путь?

Разрезать его в вершине 4 на два участка и сложить их минимумы: f(1, 4) + f(4, 100). Любой путь через 4 — это участок до 4 и участок после. Каждый не короче своего минимума, а два лучших участка всегда можно склеить в 4.

print(f(1, 4) + f(4, 100))

Получилось 2.5 + 8.0 = 10.5 — дороже, чем 7.5 без условия: лучший путь через 4 не проходит.

Если обязательных вершин две, участков три. В каком порядке их проходить, угадывать не нужно: посчитай оба порядка и возьми меньший. Например, путь из 6 в 100 через 1 и 7:

a = f(6, 1) + f(1, 7) + f(7, 100)b = f(6, 7) + f(7, 1) + f(1, 100)print(a, b, min(a, b))

Из 7 в 1 пути нет, поэтому второй порядок дал бесконечность. В графе без циклов иначе и не бывает: если бы из 1 можно было попасть в 7, а из 7 — в 1, получился бы цикл. Подходит не больше одного порядка.

А если через вершину 7 проходить нельзя?

Сделать её тупиком: в запрещённой вершине функция сразу возвращает бесконечность. Тогда ни одна стрелка в 7 не выиграет минимум — так же, как стрелка в настоящий тупик в подтеме 2.

BAN = 7  @cachedef g(v, t):    if v == BAN:        return float("inf")    if v == t:        return 0    best = float("inf")    for u, w in graph.get(v, []):        best = min(best, w + g(u, t))    return best  print(g(1, 100), g(6, 100))

Проверка запрета стоит первой: даже если запрещена сама цель, войти в неё нельзя. Для запрета пишут отдельную функцию со своим @cache: ответы f без запрета к ней не подходят.

С запретом пути может и не остаться — тогда функция вернёт inf, а int(inf) остановит программу ошибкой. В задачах экзамена пишут «существование пути гарантируется»; если такой фразы нет, сначала выведи само значение.

Путь из 6 в 100 должен пройти по ребру 6 → 7. Как это учесть?

Путь через ребро a → b — это участок до a, само ребро и участок от b: f(s, a) + вес ребра + f(b, t). Вес ребра берут из списка вершины a. dict(graph[6]) превращает список пар в словарь «куда → вес»:

print(dict(graph[6]))print(f(6, 6) + dict(graph[6])[7] + f(7, 100))

Участок до 6 пустой — путь и так начинается в 6, поэтому f(6, 6) = 0. Вышло 7.0 + 2.0 = 9, хотя без условия путь из 6 стоит 8.5.

Так же решают задачу, где заданы первое и последнее ребро пути. Из 6 в 12, первое ребро 6 → 7, последнее 100 → 12: вес первого, плюс f(7, 100), плюс вес последнего — 7.0 + 2.0 + 1.0 = 10.

• Цель — параметрf(v, t) — путь из v в t
• Через вершину kf(s, k) + f(k, t)
• Через две вершиныоба порядка, взять меньший
• В обход вершиныотдельная функция: в запрещённой вершине ∞
• Через ребро a → bf(s, a) + вес + f(b, t)
• Вес ребраdict(graph[a])[b]
• Пути нетфункция вернёт inf, int от неё — ошибка