Задание 23: кратчайший путь во взвешенном графе
Авторское
Задание выполняется с использованием прилагаемого файла.
В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W): L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите наименьшее количество рёбер в пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется.
Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000, W ≤ 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Запишите в ответе только число.
Файлы к заданию: Граф из 200 рёбер (задание 23).txt
Решить на Python прямо здесь
Программа выполняется в вашем браузере. Файлы задания уже лежат рядом с программой:
Граф из 200 рёбер (задание 23).txt — открывайте их по этому имени.
На экзамене сдаётся только ответ — впишите его в поле ниже. Ctrl+Enter — запуск.