Задание выполняется с использованием прилагаемых файлов
В текстовом файле задан ориентированный взвешенный граф, не содержащий циклов. Каждая строка описывает одно ребро и содержит три числа: L, M и W. Натуральные числа L и M — номера начальной и конечной вершин ребра, положительное вещественное число W — его вес. Между одной и той же парой вершин не бывает нескольких рёбер одного направления.
Найдите кратчайший путь из вершины 7 в вершину 941. Длина пути равна сумме весов входящих в него рёбер. Гарантируется, что хотя бы один такой путь существует.
Номера вершин не превосходят 1000 и могут идти не подряд. Вес каждого ребра не превосходит 10 000. В файле не более 200 строк. Числа разделены пробелами и/или символами табуляции, дробная часть отделена точкой. Строки с количеством вершин или рёбер в файле нет.
В ответе запишите целую часть длины кратчайшего пути.
Пример графа:
Пример содержимого файла для этого графа:
63 941 8.0
7 28 4.6
941 512 1.1
63 28 1.5
7 941 11.6
28 941 3.2
7 63 2.4
|
 |
Ответ для примера: 7.
Пример имеет иллюстративный характер. Для выполнения задания используйте прилагаемый файл.