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