Задание 23 ЕГЭ: длина пути по весам рёбер

Кратчайший или самый длинный путь по весам. Тема номера — кратчайший путь во взвешенном графе. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

В текстовом файле 23.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 881 в вершину с номером 695. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь. Существование хотя бы одного пути гарантируется.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000; W ≤ 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке

100  12   1.0
6    7    7.0
6    1    1.0
1    7    5.5
7    100  2.0
4    100  8.0
1    100  12.0
1    4    2.5

Для приведённого примера при таком же вопросе о путях из вершины 1 в вершину 100 верным ответом будет 7.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Скачать файл к примеру

Решение

Граф ациклический, поэтому кратчайший путь из v равен минимуму по рёбрам v → u величины «вес ребра + кратчайший путь из u». Вершины без выхода к конечной получают бесконечность. Как в демоверсии, подойдёт и алгоритм Беллмана — Форда: рёбер не больше 200. Длина пути равна 3079,4, её целая часть — 3079. Вещественные веса складываются с погрешностью, но длина здесь заведомо не целая, поэтому int() даёт верную целую часть.

Ответ: 3079.

from collections import defaultdict
from functools import lru_cache

g = defaultdict(list)                  # g[L] — список (M, W)
for line in open("23.txt"):
    p = line.split()                   # split() без аргументов: любые пробелы и табуляции
    if p:
        g[int(p[0])].append((int(p[1]), float(p[2])))

@lru_cache(None)
def short(v, t):                       # длина кратчайшего пути из v в t (inf — пути нет)
    if v == t:
        return 0
    return min((w + short(u, t) for u, w in g[v]), default=float("inf"))

d = short(881, 695)
print(d)                        # сама длина
print(int(d))                   # ответ — целая часть

Решить такую задачу — новый вариант с проверкой