Олимпиадный тренинг

Задача . Дейкстра: восстановление пути


Дан ориентированный взвешенный граф. Найдите кратчайший путь от одной заданной вершины до другой.
 
Входные данные
В первой строке содержатся три числа: 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
2 3 1



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w64155
C#1
Java1
Python68
Комментарий учителя