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

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