Алгоритм Дейкстры
Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от вершины S до вершины F.
Технические условия
Входные данные
В первой строке входного файла три числа: N, S и F (1 ≤ N ≤ 100; 1 ≤ S, F ≤ N), где N - количество вершин графа. В следующих N строках записаны по N чисел - матрица смежности графа, где число в i-ой строке j-ом столбце соответствует ребру из i в j: -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - наличее ребра данного веса. На главной диагонали матрицы всегда записаны нули.
Выходные данные
Вывести искомое расстояние или -1, если пути между указанными вершинами не существует.
Информация о задаче
Лимит времени: 1 секундаЛимит памяти: 64 MB
Баллы за пройденный тест: 9.09091
Сложность: 9% 135/149
Классификация: Теория графов, Алгоритм Дейкстры
Пример
Пример входных данных3 1 2 0 -1 2 3 0 -1 -1 4 0 |
Пример выходных данных6 |
| ← Магический квадрат | Список задач | Stock Exchange → |