В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W).
L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M.
Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100.
Существование хотя бы одного такого пути гарантируется.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд.
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
Для приведённого примера верным ответом будет 7.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла
Решение 1
Нужен самый короткий путь из города 1 в город 100. Считаем его рекурсией: путь из x — это одна дорога плюс кратчайший путь дальше.
🔹 Шаг 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
print(int(f(1, 100)))
📌 Читаем 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
📌 Если x == y, мы уже на месте — длина пути равна 0. @lru_cache(None) запоминает уже посчитанные f(x, y), иначе на этом файле перебор путей шёл бы слишком долго.
🔹 Шаг 3. Перебираем дороги из x
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 — «путь пока не найден». В цикле для каждой дороги (v, w) из x считаем w + f(v, y) и оставляем меньшее в m. Если дорог нет, вернётся 10**10 (тупик).
🔹 Шаг 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
print(int(f(1, 100)))
📌 Целая часть f(1, 100). Ответ: 7089.
