Что проверяет задание

В файле задан ориентированный взвешенный граф (список рёбер). Нужно найти длину кратчайшего пути из вершины с номером 1 в вершину с номером 100 и записать в ответ целую часть этой длины. Существование пути гарантируется.

Определения

Ориентированный граф (орграф), рёбра имеют направление: из L в M.

Взвешенный граф, у каждого ребра есть вес W (стоимость перехода).

Путь, последовательность рёбер, где конец предыдущего совпадает с началом следующего.

Длина пути, сумма весов рёбер пути (не число рёбер).

Кратчайший путь, путь с минимальной длиной среди всех путей из старта в финиш.

Ациклический граф (DAG), ориентированный граф без циклов. В типовой формулировке ЕГЭ граф ациклический, веса положительные.

Целая часть положительного числа x, результат int(x) в Python (отбрасывание дробной части), например 7.5 → 7.

Связь с файлом

Каждая строка файла: L M W - ребро из L в M веса W. Числа разделены пробелами или табуляциями. Вершины могут быть пронумерованы не подряд. Параллельных рёбер между одной парой вершин нет.

Типовой пример в условии иллюстративный; считать нужно по прилагаемому файлу 23.txt.

Общий алгоритм решения

1. Прочитать все рёбра и построить список смежности: из вершины u выходят пары (v, w).
2. Найти кратчайшее расстояние от 1 до 100. При неотрицательных весах подходит алгоритм Дейкстры; на DAG можно считать динамикой в топологическом порядке.
3. Ответ: целая часть найденного расстояния - int(dist[100]).
4. Проверить на маленьком примере из условия (если он совпадает с вашим кодом по логике): путь 1 → 7 → 100 длины 7.5 даёт ответ 7.

Программа построчно

Граф записан в файле списком рёбер: в каждой строке - откуда (L), куда (M) и вес (W). Программа читает рёбра в словарь и рекурсивно перебирает пути от начальной вершины к конечной.

Разберём программу на условии:

Найдите целую часть длины кратчайшего пути из вершины 1 в вершину 100.

d = {}
for s in open("23.txt"):
    L, M, W = s.split()
    L, M, W = int(L), int(M), float(W)
    if L in d:
        d[L].append([M, W])
    else:
        d[L] = [[M, W]]

def f(x, length):
    if x == 100:
        return length
    if x in d:
        return min(f(y, length + w) for y, w in d[x])
    return 10 ** 10

print(int(f(1, 0)))

Первые восемь строк - читаем граф из файла в словарь d. Подробно - в разделе «Граф в словаре».

def f(x, length): - функция идёт по графу: x - вершина, в которой мы сейчас, length - длина уже пройденной части пути. Подробно - в разделе «Функция f: перебор путей».

if x == 100: / return length - дошли до конца: длина пути найдена.

if x in d: / return min(f(y, length + w) for y, w in d[x]) - из вершины x выходят рёбра; пробуем пойти по каждому и выбираем наименьшую длину. Подробно - в разделе «Кратчайший путь: min».

return 10 ** 10 - из вершины x рёбер нет, а до конца не дошли: тупик. Возвращаем огромное число, чтобы такой «путь» никогда не оказался кратчайшим.

print(int(f(1, 0))) - начинаем в вершине 1 с нулевой длиной; int берёт целую часть. Подробно - в разделе «Округление ответа».

Граф в словаре

d = {}
for s in open("23.txt"):
    L, M, W = s.split()
    L, M, W = int(L), int(M), float(W)
    if L in d:
        d[L].append([M, W])
    else:
        d[L] = [[M, W]]

• d = {} - пустой словарь. Ключ - номер вершины, значение - список рёбер, выходящих из неё. Например, d[1] = [[966, 98.5], [135, 258.5]]: из вершины 1 есть ребро в 966 с весом 98,5 и ребро в 135 с весом 258,5;
• for s in open("23.txt"): - перебираем строки файла;
• s.split() - режем строку по пробелам и табуляциям (их в файле может быть сколько угодно) на три куска;
• int(L), int(M), float(W) - номера вершин целые, вес - дробное число;
• если для вершины L список уже есть - дописываем ребро (append), иначе создаём список из одного ребра.

Номера вершин могут идти не подряд (1, 135, 966, …) - словарь это не смущает: он хранит только те вершины, которые есть.

Функция f: перебор путей

def f(x, length):
    if x == 100:
        return length
    if x in d:
        return min(f(y, length + w) for y, w in d[x])
    return 10 ** 10

Функция вызывает саму себя для каждой следующей вершины:

• for y, w in d[x] - перебираем рёбра из x: y - куда ведёт ребро, w - его вес;
• f(y, length + w) - переходим в y, длина пути увеличилась на вес ребра;
• по цепочке вызовов программа проходит все пути из начальной вершины. Граф ациклический (без циклов), поэтому каждый путь когда-нибудь закончится - в конечной вершине или в тупике.

Кратчайший путь: min

min(… for y, w in d[x]) - из всех продолжений пути выбираем самое короткое. Так на каждом шаге остаётся лучший вариант, и в итоге f(1, 0) - длина кратчайшего пути из 1 в 100.

10 ** 10 в тупике нужен именно для min: огромное число никогда не окажется наименьшим, если есть настоящий путь.

Самый длинный путь: max

Для самого длинного пути - то же самое, но max, а в тупике - очень маленькое число:

def f(x, length):
    if x == 100:
        return length
    if x in d:
        return max(f(y, length + w) for y, w in d[x])
    return -10 ** 10

-10 ** 10 в тупике гарантирует, что путь, который не дошёл до конца, не победит в max.

Путь через вершину

«Путь из 1 в 100, проходящий через вершину 177» состоит из двух частей: из 1 в 177 и из 177 в 100. Кратчайший такой путь - сумма двух кратчайших частей.

def f(x, finish, length):
    if x == finish:
        return length
    if x in d:
        return min(f(y, finish, length + w) for y, w in d[x])
    return 10 ** 10

print(int(f(1, 177, 0) + f(177, 100, 0) + 0.5))

Конечная вершина стала параметром finish, чтобы одной функцией считать обе части.

Количество путей: sum

def f(x):
    if x == 100:
        return 1
    if x in d:
        return sum(f(y) for y, w in d[x])
    return 0

• дошли до конца - это один путь: return 1;
• из вершины x путей столько, сколько в сумме путей из всех вершин, куда из x ведут рёбра: sum(…);
• тупик - ноль путей.

Количество кратчайших путей

Здесь для каждой вершины нужно знать сразу два числа: длину кратчайшего пути до конца и сколько таких путей.

@lru_cache(None)
def f(x):
    if x == 100:
        return 0, 1
    best, count = 10 ** 10, 0
    for y, w in d.get(x, []):
        length, ways = f(y)
        if w + length < best:
            best, count = w + length, ways
        elif w + length == best:
            count += ways
    return best, count

print(f(1)[1])

• функция возвращает пару (длина, количество); из конечной вершины - путь длины 0, и он один;
• d.get(x, []) - список рёбер x, а если рёбер нет - пустой список (тупик);
• нашли путь короче лучшего - запоминаем новую длину, а количество берём от вершины y;
• нашли путь такой же длины - прибавляем его пути к количеству;
• f(1)[1] - второй элемент пары, то есть количество.

Ускорение: lru_cache

Когда рёбер сотни, путей могут быть миллиарды, и полный перебор не закончится за разумное время. Тогда функцию переписывают так, чтобы её ответ зависел только от вершины: f(x) - длина лучшего пути из x до конца. Ответ для каждой вершины одинаков, с какой бы стороны мы в неё ни пришли, поэтому его можно запомнить:

from functools import lru_cache

@lru_cache(None)
def f(x):
    if x == 100:
        return 0
    if x in d:
        return min(w + f(y) for y, w in d[x])
    return 10 ** 10

print(int(f(1)))

• w + f(y) - вес ребра плюс лучший путь из y;
• @lru_cache(None) запоминает f(x) для каждой вершины - каждая считается один раз, и программа работает мгновенно.

Количество путей через вершину

Путь из 1 в 100 через вершину 25 - это часть из 1 в 25 и часть из 25 в 100. Любую первую часть можно продолжить любой второй, поэтому количества перемножаются:

def f(x, finish):
    if x == finish:
        return 1
    if x in d:
        return sum(f(y, finish) for y, w in d[x])
    return 0

print(f(1, 25) * f(25, 100))

Если из 1 в 25 ведут 3 пути, а из 25 в 100 - 4 пути, то путей через 25 всего 3 · 4 = 12. Для «пути через ребро 25 → 50» то же самое: f(1, 25) * f(50, 100) - само ребро добавляет ровно один способ пройти от 25 к 50.

Порядок обязательных вершин

«Путь через вершины 91 и 474» - порядок не сказан. Но граф ациклический: если из 91 можно дойти до 474, то из 474 вернуться в 91 нельзя (иначе был бы цикл). Значит, порядок определяется графом, и он единственный: путь идёт 1 → … → 91 → … → 474 → … → 100.

print(int(f(1, 91) + f(91, 474) + f(474, 100)))

Проверить порядок можно той же функцией: f(474, 91) вернёт 10 ** 10 - пути нет. Если в условии сказано «сначала через 25, а затем через 50», порядок уже задан.

Путь через ребро

«Путь, проходящий по ребру из 312 в 46» состоит из трёх кусков: кратчайший путь до 312, само ребро 312 → 46 и кратчайший путь от 46 до конца.

w1 = dict(d[312])[46]
print(int(f(1, 312) + w1 + f(46, 100)))

• d[312] - список пар [куда, вес] для рёбер из вершины 312;
• dict(d[312]) превращает его в словарь «куда → вес», и [46] даёт вес нужного ребра.

Так же решается «первое ребро пути - из 2691 в 2840, последнее - из 9180 в 9514»: w1 + f(2840, 9180) + w2.

Запреты: убираем вершину или ребро

«Не проходящий через вершину 96», «не проходящий по ребру 59 → 698», «только рёбра с весом не менее 10» - проще всего выполнить при чтении файла: такие рёбра не кладём в словарь. Тогда любой путь, который найдёт функция, запрет соблюдает сам, и саму функцию менять не нужно.

d = {}
for s in open("23.txt"):
    L, M, W = s.split()
    L, M, W = int(L), int(M), float(W)
    if L == 96 or M == 96:
        continue
    if L in d:
        d[L].append([M, W])
    else:
        d[L] = [[M, W]]

• continue - перейти к следующей строке файла, не добавляя ребро;
• вершина 96: убираем все рёбра, которые в неё входят или из неё выходят (L == 96 or M == 96) - в неё нельзя войти;
• ребро 59 → 698: if (L, M) == (59, 698):;
• лёгкие рёбра: if W < 10:.

Запреты сочетаются с обязательными вершинами: сначала убираем лишнее из графа, потом режем путь на части.

Количество рёбер в пути

Если спрашивают не длину, а число рёбер, каждое ребро добавляет к пути 1, а не свой вес:

@lru_cache(None)
def f(x):
    if x == 100:
        return 0
    if x in d:
        return min(1 + f(y) for y, w in d[x])
    return 10 ** 10

Для наибольшего числа рёбер - max(1 + f(y) …) и -10 ** 10 в тупике, как в разделе «Самый длинный путь: max».

Ограничение на число рёбер

«Путь, содержащий не более 20 рёбер»: теперь ответ зависит не только от вершины, но и от того, сколько рёбер ещё можно взять. Добавляем параметр k - запас рёбер:

@lru_cache(None)
def f(x, k):
    if x == 100:
        return 0
    if k == 0:
        return 10 ** 10
    if x in d:
        return min(w + f(y, k - 1) for y, w in d[x])
    return 10 ** 10

print(int(f(1, 20)))

• каждое ребро тратит единицу запаса: k - 1;
• запас кончился (k == 0), а до конца не дошли - такой путь не годится;
• @lru_cache запоминает ответ для каждой пары (вершина, запас).

Для «количества путей ровно из 25 рёбер» в конечной вершине путь засчитывается, только если запас истрачен полностью: return 1 if k == 0 else 0, а вместо min - sum. Для длины «ровно из 14 рёбер» то же самое: return 0 if k == 0 else 10 ** 10.

«Путь, состоящий не менее чем из 15 рёбер» - наоборот: k - сколько рёбер ещё обязательно пройти. Запас здесь не кончается: путь может быть сколь угодно длинным, поэтому строки if k == 0 нет, а уменьшаем k только до нуля:

@lru_cache(None)
def f(x, k):
    if x == 100:
        return 0 if k == 0 else 10 ** 10
    if x in d:
        return min(w + f(y, max(k - 1, 0)) for y, w in d[x])
    return 10 ** 10

print(int(f(1, 15)))

• max(k - 1, 0) - прошли ребро: обязательных рёбер осталось на одно меньше, но не меньше нуля;
• в конечной вершине путь годится, только если обязательные рёбра набраны (k == 0), иначе - огромное число, и min его не выберет.

Наибольший вес ребра на пути

«Максимальный вес пути» - это вес самого тяжёлого ребра на нём. Нужен путь, у которого он как можно меньше:

@lru_cache(None)
def f(x):
    if x == 100:
        return 0
    if x in d:
        return min(max(w, f(y)) for y, w in d[x])
    return 10 ** 10

• max(w, f(y)) - самое тяжёлое ребро пути, который начинается ребром веса w и продолжается лучшим путём из y;
• min(…) - из всех продолжений выбираем то, где самое тяжёлое ребро легче всего;
• в конечной вершине путь пустой - 0 никогда не победит в max настоящее ребро.

Два критерия сразу: пара чисел

«Найдите кратчайший путь; если таких несколько, выберите тот, где рёбер меньше; в ответ - число рёбер». Функция возвращает пару (длина, рёбра), а пары Python сравнивает по очереди: сначала первые элементы, при равенстве - вторые. Поэтому min сам выберет нужный путь:

@lru_cache(None)
def f(x):
    if x == 100:
        return 0, 0
    best = (10 ** 10, 0)
    for y, w in d.get(x, []):
        length, edges = f(y)
        best = min(best, (w + length, 1 + edges))
    return best

print(f(1)[1])

• (3, 7) < (3, 9) < (4, 1) - так сравниваются пары;
• f(1)[1] - второй элемент пары: число рёбер.

Если главный критерий - число рёбер, а при равенстве - сумма весов, пару ставим наоборот: (1 + edges, w + length).

Путь до тупика

«Тупик» - вершина, из которой не выходит ни одного ребра. В словаре d такой вершины нет как ключа. Если путь может закончиться в любом тупике, конечная вершина не нужна - конец там, где рёбер нет:

@lru_cache(None)
def f(x):
    if x not in d:
        return 0
    return max(w + f(y) for y, w in d[x])

Глубина рекурсии

Каждый шаг по ребру - это ещё один вложенный вызов f. Python по умолчанию разрешает около 1000 вложенных вызовов, а в графе на десятки тысяч рёбер путь может быть длиннее. Тогда в начале программы поднимаем предел:

import sys
sys.setrecursionlimit(100000)

Вручную: считаем от конца

Если граф маленький (десяток рёбер), ответ можно найти без программы - той же идеей, что у функции с lru_cache. Обозначим f(v) - ответ для пути из вершины v до конца (длину кратчайшего пути, число путей…). Для конечной вершины он известен сразу, а для любой другой вершины выражается через вершины, куда из неё ведут рёбра. Поэтому считаем от конца к началу:

1. Выписываем только нужные рёбра - те, по которым можно пройти из начала в конец. Вершины, в которые из начала не попасть или из которых не дойти до конца, вычёркиваем.
2. Конечная вершина: f(100) = 0 (для числа путей - 1: путь уже закончился, и он один).
3. Берём вершину, у которой все рёбра ведут в уже посчитанные вершины, и считаем её по правилу:
   • кратчайший путь: f(v) = min(вес ребра + f(куда ведёт ребро)) по всем рёбрам из v;
   • самый длинный путь - то же с max;
   • число путей: f(v) - сумма f всех вершин, куда ведут рёбра из v;
   • число рёбер: вместо веса каждое ребро даёт 1.
4. Повторяем, пока не дойдём до начальной вершины: f(1) - ответ.

Пример на графе из условия (кратчайший путь из 1 в 100):

f(100) = 0
f(7) = 2 + f(100) = 2
f(4) = 8 + f(100) = 8
f(1) = min(5,5 + f(7); 12 + f(100); 2,5 + f(4)) = min(7,5; 12; 10,5) = 7,5

Целая часть - 7. Дробные веса удобно складывать в столбик: вручную погрешности, как у компьютера, нет.

Округление ответа

• «целая часть длины» → int(x): дробная часть отбрасывается, 25,9 → 25;
• «округлённую до ближайшего целого (0,5 округляется вверх)» → int(x + 0.5): 7,5 → 8, 7,4 → 7.

Встроенная функция round здесь не подходит: она округляет половину к чётному числу, round(2.5) даёт 2, а нужно 3.

Дробные веса и int

Веса вроде 43.9 и 4.5 компьютер хранит неточно, и сумма может получиться 3362.9999999 вместо точных 3363. Тогда int отбросит дробную часть и даст 3362 - ответ на единицу меньше. Защита - округлить сумму до нескольких знаков перед int:

print(int(round(f(1), 6)))

round(x, 6) убирает «хвост» погрешности, а настоящую дробную часть (например, .5) не трогает.