(А. Богданов) В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W).
L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M.
Таким образом, количество строк в файле равно количеству рёбер в графе.
Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 4 в вершину с номером 96, проходящего через вершину с номером 25.
Существование хотя бы одного такого пути гарантируется.
Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд.
L ≤ 1000, M ≤ 1000; W ≤ 10 000.
Количество строк в файле не превосходит 200.
Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке.
97 805 1.0
604 201 7.0
604 3 1.0
3 201 5.5
201 97 2.0
302 97 8.0
3 97 12.0
3 302 2.5
Для приведённого примера, при поиске кратчайшего пути из вершины 6 в вершину 100, проходящего через вершину 4, верным ответом будет 11.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла
Решение 1
Нужен самый короткий путь из города 4 в город 96, обязательно через вершину 25.
Идея: путь = «4 → 25» + «25 → 96». Длину каждого участка считаем рекурсией.
🔹 Шаг 1. Собираем граф
from functools import lru_cache
g = {}
for line in open('23.txt'):
a, b, c = map(float, line.split())
g.setdefault(a, []).append((b, c))
@lru_cache(None)
def f(x, y):
if x == y:
return 0
m = 10**10
for v, w in g.get(x, []):
m = min(m, w + f(v, y))
return m
# путь 4 → 25 → 96
print(int(f(4, 25) + f(25, 96)))
📌 Читаем 23.txt построчно. В g[a] кладём пары (b, c).
🔹 Шаг 2. База рекурсии
from functools import lru_cache
g = {}
for line in open('23.txt'):
a, b, c = map(float, line.split())
g.setdefault(a, []).append((b, c))
@lru_cache(None)
def f(x, y):
if x == y:
return 0
📌 lru_cache ускоряет повторные вызовы. Если x == y, длина пути равна 0.
🔹 Шаг 3. Перебираем соседей
from functools import lru_cache
g = {}
for line in open('23.txt'):
a, b, c = map(float, line.split())
g.setdefault(a, []).append((b, c))
@lru_cache(None)
def f(x, y):
if x == y:
return 0
m = 10**10
for v, w in g.get(x, []):
m = min(m, w + f(v, y))
return m
📌 Сначала m = 10**10. В цикле для каждой дороги считаем w + f(v, y) и оставляем меньшее в m.
🔹 Шаг 4. Складываем два участка
from functools import lru_cache
g = {}
for line in open('23.txt'):
a, b, c = map(float, line.split())
g.setdefault(a, []).append((b, c))
@lru_cache(None)
def f(x, y):
if x == y:
return 0
m = 10**10
for v, w in g.get(x, []):
m = min(m, w + f(v, y))
return m
# путь 4 → 25 → 96
print(int(f(4, 25) + f(25, 96)))
📌 Считаем f(4, 25) + f(25, 96), берём целую часть. Ответ: 735.
