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