Задание выполняется с использованием прилагаемого файла.
В текстовом файле описан ориентированный взвешенный граф без циклов.
Каждая строка содержит два натуральных числа L и M и положительное вещественное число W.
Эта строка задаёт ребро из вершины L в вершину M с весом W.
Для одной и той же пары вершин в файле не бывает двух рёбер.
Найдите целую часть длины кратчайшего пути из вершины 1 в вершину 100.
Длина пути равна сумме весов входящих в него рёбер.
Существование пути гарантируется.
Для выполнения задания напишите программу.
Номера вершин могут идти с пропусками.
Значения L и M не превышают 1000, значение W — 10 000.
В файле не более 200 строк.
Числа в строке разделены пробелами и/или знаками табуляции.
Решение 1
Представь города и дороги между ними. Нужно добраться из города 1 в город 100 по самому короткому пути (сумма весов дорог минимальна). Ответ — целая часть этой длины.
🔹 Шаг 1. Заводим список длин путей
d = [0, 0] + [float('inf')] * 1000
data = open('23_31904.txt').read().split()
for _ in range(200):
for i in range(0, len(data), 3):
u, v, w = int(data[i]), int(data[i+1]), float(data[i+2])
d[v] = min(d[v], d[u] + w)
print(int(d[100]))
📌 Список d: номер в списке — номер города. В d[1] сразу ставим 0 (мы стартуем из города 1). В остальные ячейки — «бесконечность» (float('inf')): путь туда пока неизвестен.
🔹 Шаг 2. Читаем файл с дорогами
d = [0, 0] + [float('inf')] * 1000
data = open('23_31904.txt').read().split()
📌 Открываем файл 23_31904.txt, читаем всё и режем на числа. Дальше берём их тройками: откуда → куда, и вес этой дороги.
🔹 Шаг 3. Ищем более короткие пути
d = [0, 0] + [float('inf')] * 1000
data = open('23_31904.txt').read().split()
for _ in range(200):
for i in range(0, len(data), 3):
u, v, w = int(data[i]), int(data[i+1]), float(data[i+2])
d[v] = min(d[v], d[u] + w)
📌 Повторяем до 200 раз (дорог не больше двухсот). Для каждой дороги из u в v с весом w спрашиваем: «А если пойти через u, путь до v станет короче?» Если да — записываем d[v] = d[u] + w. Так постепенно находятся самые короткие пути.
🔹 Шаг 4. Печатаем ответ
print(int(d[100]))
📌 В d[100] лежит длина пути до города 100. Берём целую часть через int(...) и печатаем. Ответ: 2886.
