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