e-olymp
Змагання

Dijkstra algorithm

Алгоритм Дейкстри

Дано орієнтований зважений граф. Знайти найкоротшу відстань від вершини s до вершини f.

Вхідні дані

У першому рядку задано три числа n, s та f (1n100, 1s, fn), де n - кількість вершин графа. В наступних n рядках записано по n чисел - матриця суміжності графа, де число в i-ому рядку та j-ому стовпчику відповідає ребру з i в j: -1 означає відсутність ребра між вершинами, а довільне невід'ємне число - наявність ребра даної ваги. На головній діагоналі матриці завжди записано нулі.

Вихідні дані

Вивести шукану відстань або -1, якщо шляху між заданими вершинами не існує.

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