eolymp
Задачи

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

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

Дан ориентированный взвешенный граф. Найти кратчайшее расстояние от вершины 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