eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дейкстра

Дейкстра

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.

Входные данные

В первой строке содержится три числа n, s и f (1n2000; 1s, fn), где n - количество вершин графа, s - начальная вершина, а f - конечная. В следующих n строках по n чисел - матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. На главной диагонали матрицы всегда записаны нули.

Выходные данные

Вывести искомое расстояние или -1, если пути не существует.

prb2351.gif

Пример

Входные данные #1
3 1 2
0 -1 2
3 0 -1
-1 4 0
Выходные данные #1
6