|
Алгоритм Дейкстры - 2
(Время: 1 сек. Память: 16 Мб Сложность: 53%)
Дан ориентированный взвешенный граф. Найдите кратчайший путь от одной заданной вершины до другой.
Входные данные
В первой строке входного файла INPUT.TXT содержатся три целых числа: N, S и F (1 ≤ N ≤ 100, 1 ≤ S, F ≤ N), где N – количество вершин графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.
Выходные данные
В выходной файл OUTPUT.TXT выведите последовательно все вершины одного (любого) из кратчайших путей, или одно число -1, если пути между указанными вершинами не существует.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3 2 1
0 1 1
4 0 1
2 1 0 | 2 3 1 |
2 | 4 2 3
0 -1 -1 -1
1 0 -1 1
1 -1 0 1
-1 -1 -1 0 | -1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |