Во входном текстовом файле задан ациклический ориентированный взвешенный граф.
Строка файла — это тройка: два натуральных числа L, M и положительное вещественное W.
L — начало ребра, M — конец, W — его вес.
Сколько строк в файле — столько рёбер в графе.
Две вершины соединяет не больше одного ребра.
Нужно вычислить целую часть длины кратчайшего пути из вершины 1 в вершину 87 и записать её в ответ.
Путь из 1 в 87 существует.
Длина пути — сумма весов рёбер на маршруте; ищем минимальную такую сумму.
Решение оформляется программой.
Вершины могут иметь номера не по порядку.
Известно: 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 в город 87 по самому короткому пути (сумма весов дорог минимальна). Ответ — целая часть этой длины.
🔹 Шаг 1. Заводим список длин путей
d = [0, 0] + [float('inf')] * 1000
data = open('23.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[87]))
📌 Список d: номер в списке — номер города. В d[1] сразу ставим 0 (мы стартуем из города 1). В остальные ячейки — «бесконечность» (float('inf')): путь туда пока неизвестен.
🔹 Шаг 2. Читаем файл с дорогами
d = [0, 0] + [float('inf')] * 1000
data = open('23.txt').read().split()
📌 Открываем файл 23.txt, читаем всё и режем на числа. Дальше берём их тройками: откуда → куда, и вес этой дороги.
🔹 Шаг 3. Ищем более короткие пути
d = [0, 0] + [float('inf')] * 1000
data = open('23.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[87]))
📌 В d[87] лежит длина пути до города 87. Берём целую часть через int(...) и печатаем. Ответ: 7958.
