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

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

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

В первой строке входного файла три числа: 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 раз повторяем шаг алгоритма:

• Находим вершину, из которой мы еще не ходили, и текущее расстояние до которой минимально (для поиска такой вершины рекомендуется воспользоваться функцией, написанной в предыдущей задаче).
• Ходим из этой вершины, т.е.:
  • Перебираем все соседние с ней вершины - проверяем, если расстояние до вершины, из которой мы ходим + ребро из нее в рассматриваемую вершину меньше, чем расстояние до этой вершины, уменьшаем расстояние до этой вершины
  • Помечаем, что мы "походили" из этой вершины.

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