Что проверяет задание
В файле задан ориентированный взвешенный граф (список рёбер). Нужно найти длину кратчайшего пути из вершины с номером 1 в вершину с номером 100 и записать в ответ целую часть этой длины. Существование пути гарантируется.
Определения
Ориентированный граф (орграф), рёбра имеют направление: из L в M.
Взвешенный граф, у каждого ребра есть вес W (стоимость перехода).
Путь, последовательность рёбер, где конец предыдущего совпадает с началом следующего.
Длина пути, сумма весов рёбер пути (не число рёбер).
Кратчайший путь, путь с минимальной длиной среди всех путей из старта в финиш.
Ациклический граф (DAG), ориентированный граф без циклов. В типовой формулировке ЕГЭ граф ациклический, веса положительные.
Целая часть положительного числа x, результат int(x) в Python (отбрасывание дробной части), например 7.5 → 7.
Связь с файлом
Каждая строка файла: L M W - ребро из L в M веса W. Числа разделены пробелами или табуляциями. Вершины могут быть пронумерованы не подряд. Параллельных рёбер между одной парой вершин нет.
Типовой пример в условии иллюстративный; считать нужно по прилагаемому файлу 23.txt.
Общий алгоритм решения
- Прочитать все рёбра и построить список смежности: из вершины u выходят пары (v, w).
- Найти кратчайшее расстояние от 1 до 100. При неотрицательных весах подходит алгоритм Дейкстры; на DAG можно считать динамикой в топологическом порядке.
- Ответ: целая часть найденного расстояния -
int(dist[100]). - Проверить на маленьком примере из условия (если он совпадает с вашим кодом по логике): путь 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)для каждой вершины - каждая считается один раз, и программа работает мгновенно.
Округление ответа
- «целая часть длины» →
int(x): дробная часть отбрасывается, 25,9 → 25; - «округлённую до ближайшего целого (0,5 округляется вверх)» →
int(x + 0.5): 7,5 → 8, 7,4 → 7.
Встроенная функция round здесь не подходит: она округляет половину к чётному числу, round(2.5) даёт 2, а нужно 3.