Задачі
Дейкстра
Дейкстра
Задано орієнтовний зважений граф. Знайдіть найкоротшу відстань від однієї заданої вершини до іншої.
Вхідні дані
У першому рядку міститься три числа n, s та f (1 ≤ n ≤ 2000, 1 ≤ s, f ≤ n), де n - кількість вершин графа, s - початкова вершина, а f - кінцева. У наступних n рядках по n чисел - матриця суміжності графа, де -1 означає відсутність ребра між вершинами, а довільне невід'ємне число - присутність ребра заданої ваги. На головній діагонали матриці завжди записані нулі.
Вихідні дані
Вивести шукану відстань або -1, якщо шляху не існує.
Вхідні дані #1
3 1 2 0 -1 2 3 0 -1 -1 4 0
Вихідні дані #1
6