Задача "Дейкстра"

Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от одной заданной вершины до другой.

Входные данные:

В первой строке входного файла три числа: N, S и F (1 ≤ N ≤ 100; 1 ≤ S, F ≤ N), где N - количество вершин графа, S - начальная вершина, а F - конечная. В следующих N строках по N чисел - матрица смежности графа, где число в i-ой строке j-ом столбце соответствует ребру из i в j: -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. На главной диагонали матрицы - всегда нули. Веса ребер не превышают 100.

Выходные данные:

Вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

Пример входного файла:
3 1 2
0 -1 2
3 0 -1
-1 4 0

Пример выходного файла:
6

Описание алгоритма Дейкстры

Храним массив кратчайших уже найденных путей до каждой из вершин. Кроме того, нам понадобится массив с информацией - ходили ли мы уже из данной вершины или нет. Вначале расстояние до начальной вершины - 0, до остальных - бесконечность. Ни из одной вершины мы пока еще не ходили.

N раз повторяем шаг алгоритма:

После окончания мы получим массив кратчайших путей.