Дан текстовый файл с описанием ациклического ориентированного взвешенного графа.
Каждая строка файла содержит два натуральных числа (L, M) и одно положительное вещественное число (W).
Числа L и M — номера вершин, W — вес ориентированного ребра из L в M.
Число строк файла совпадает с числом рёбер.
Между двумя вершинами не может быть более одного ребра.
Требуется найти целую часть длины кратчайшего пути из вершины 1 в вершину 100 и записать её в ответе.
Хотя бы один путь из 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 по самому короткому пути (сумма весов дорог минимальна). Ответ — целая часть этой длины.
🔹 Шаг 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[100]))
📌 Список 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[100]))
📌 В d[100] лежит длина пути до города 100. Берём целую часть через int(...) и печатаем. Ответ: 16.
