В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа \((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. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла. Файл к заданию: https://drive.google.com/file/d/10R6tom9V7Z4VL4TYjBtaeAomfYG_MItv/view?usp=drive_link

Способ 1. Перебор всех путей (самый простой) Так как граф небольшой, то можно пройти всеми возможными путями и выбрать минимальный используя рекурсивный DFS (обход графа в глубину). # Объявляем список смежности graph = {} with open("23.txt") as f: for line in f: l, m, w = line.split() l = int(l) m = int(m) w = float(w) if l not in graph: graph[l] = [] graph[a].append((m, w)) # Ищем все пути def dfs(v, current_sum): global answer # Достигли конечной вершины if v == 100: answer = min(answer, current_sum) return # Перебираем все исходящие ребра for to, weight in graph.get(v, []): dfs(to, current_sum + weight) answer = float("inf") dfs(1, 0) print(int(answer)) Ответ: 10971. Способ 2. Алгоритм Дейкстры (классический подход) Данный алгоритм работает для любых ориентированных графов и положительных весов. import heapq # Объявляем список смежности graph = {} with open("23.txt") as f: for line in f: l, m, w = line.split() l = int(l) m = int(m) w = float(w) graph.setdefault(l, []).append((m, w)) # Объявим словарь для хранения всех расстояний до вершин dist = {} # Объявим очередь с приоритетом: (расстояние, вершина) queue = [(0, 1)] # Расстояние до начальной вершины всегда нулевое dist[1] = 0 # Пока в очереди есть вершины для обработки while queue: # Берём вершину с самым маленьким расстоянием current_dist, v = heapq.heappop(queue) # Если нашли лучший путь раньше if current_dist > dist[v]: continue # Дошли до конечной вершины if v == 100: break # Перебираем все вершины, в которые можно попасть из v for to, weight in graph.get(v, []): # Рассчитываем новый возможный путь: путь до текущей вершины + вес нового ребра new_dist = current_dist + weight # Если вершина ещё не посещалась или нашли более короткий путь, обновляем расстояние if to not in dist or new_dist < dist[to]: # Запоминаем лучший найденный путь dist[to] = new_dist # Добавляем новую вершину в очередь # В следующий раз алгоритм обработает вершину с минимальным расстоянием heapq.heappush( queue, (new_dist, to) ) # Используем int(), так как требуется целая часть длины пути print(int(dist[100])) Ответ: 10971. Способ 3. Топологическая сортировка + динамическое программирование (самый идеальный) Сначала получаем порядок вершин, в котором все рёбра идут только слева направо, затем считаем минимальные расстояния. from collections import deque # Объявляем список смежности графа graph = {} # Количество входящих рёбер для каждой вершины indegree = {} # Список всех вершин графа vertices = set() with open("23.txt") as f: for line in f: l, m, w = line.split() l = int(l) m = int(m) w = float(w) # Добавляем вершины vertices.add(l) vertices.add(m) # Добавляем ребро l -> m graph.setdefault(l, []).append((m, w)) # Считаем количество входящих рёбер indegree[b] = indegree.get(m, 0) + 1 indegree.setdefault(l, 0) # Начинаем топологическую сортировку queue = deque() # В очередь добавляем вершины, в которые ничего не входит for v in vertices: if indegree[v] == 0: queue.append(v) order = [] while queue: v = queue.popleft() order.append(v) # Удаляем исходящие рёбра вершины for to, w in graph.get(v, []): indegree[to] -= 1 # Если больше нет входящих рёбер, вершину можно обработать if indegree[to] == 0: queue.append(to) # Начинаем поиск кратчайшего пути INF = float("inf") # dp[v] — минимальный вес пути из вершины 1 в вершину v dp = {v: INF for v in vertices} # Начальная вершина имеет путь длины 0 dp[1] = 0 # Идём по вершинам в правильном порядке for v in order: # Проверяем все исходящие рёбра for to, w in graph.get(v, []): # Если через вершину v путь короче, обновляем расстояние if dp[v] + w < dp[to]: dp[to] = dp[v] + w print(int(dp[100])) Ответ: 10971.