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