Решение задачи №1368 «Флойд вместо Дейкстры» с ACMP





Решение задачи №1368 «Флойд вместо Дейкстры» с ACMP

Условие задачи

Дан ориентированный взвешенный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины S в вершину T.

Входные данные
В первой строке входного файла INPUT.TXT заданы натуральные числа: N, S и T – число вершин в графе, номера вершин начала и конца пути (N ≤ 50). Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершины в j-ую. Длины могут принимать любые значения от 0 до 106, число -1 означает отсутствие соответствующего ребра. Гарантируется, что на главной диагонали матрицы стоят нули.

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – минимальную длину пути. Если пути не существует, выведите -1.



Условия задач взяты с сайта acmp.ru