e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Dijkstra algorithm

Дейкстра

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

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

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

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

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

prb2351.gif

Лимит времени 2 секунды
Лимит использования памяти 128 MiB
Входные данные #1
3 1 2
0 -1 2
3 0 -1
-1 4 0
Выходные данные #1
6