Задание 23 ЕГЭ: кратчайший путь с ограничениями

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

Пример

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

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

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

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

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

Решение

Путь по ребру a → b складывается из кратчайшего пути до a, веса ребра и кратчайшего пути от b. Длина равна 3372,2, целая часть — 3372; длина заведомо не целая, поэтому int() не ошибётся из-за погрешности.

Ответ: 3372.

from collections import defaultdict
from functools import lru_cache

g = defaultdict(list)
for line in open('23.txt'):
    p = line.split()
    if p:
        g[int(p[0])].append((int(p[1]), float(p[2])))
BAN = None                      # запрещённая вершина (если есть) — задаётся ниже

@lru_cache(None)
def short(v, t):
    if v == t:
        return 0
    best = float('inf')
    for u, w in g[v]:
        if u != BAN:
            best = min(best, w + short(u, t))
    return best

w = dict(g[227])[928]
d = short(51, 227) + w + short(928, 849)
print(int(d))

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