Войти
или
Зарегистрироваться
Курсы
Учебник
Учебник 2.0
Экзамены
Олимпиады
Рубрикатор
Компилятор
Курсы
Теория графов
Алгоритм Дейкстры
Модуль:
Алгоритм Дейкстры
Задача
2
/14
Дейкстра
Теория
Нажмите, чтобы прочитать/скрыть
https://foxford.ru/wiki/informatika/algoritm-deykstry
Задача
Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.
Входные данные
В первой строке содержатся три числа: N, S и F (1≤ N≤ 100, 1≤ S, F≤ N), где N – количество вершин графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.
Выходные данные
Требуется вывести искомое расстояние или -1, если пути между указанными вершинами не существует.
Примеры
№
Входные данные
Выходные данные
1
3 2 1
0 1 1
4 0 1
2 1 0
3
1000
ms
256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач
Статистика успешных решений по компиляторам
Кол-во
С++ Mingw-w64
213
Java
1
Python
109
Комментарий учителя