(Э. Носиров) Задание выполняется с использованием файла 23.txt.
В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W).
Эта строка задаёт ориентированное ребро из вершины L в вершину M с весом W.
Граф не содержит циклов; повторных рёбер нет.
Найдите целую часть длины кратчайшего пути из вершины 1 в вершину 100.
Длина пути равна сумме весов его рёбер.
Существование такого пути гарантируется.
Для выполнения задания напишите программу.
Номера вершин могут идти с пропусками и не задают топологический порядок.
Они не превышают 1000; вес ребра не превышает 10 000.
Файл содержит 196 строк без заголовка.
Поля разделены пробелами и/или табуляциями; десятичная часть веса отделяется точкой.
Пример представления данных:
1 10 2.4
10 45 1.8
1 45 6.1
45 70 2.6
70 100 1.3
45 100 5.9
1 100 12.8
Для этого примера кратчайший путь имеет длину 8,1; его целая часть равна 8.
Пример иллюстрирует формат данных; для решения используйте прилагаемый файл.
Решение 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). Ответ: 522.
