|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 06-2. Алгоритм Дейкстры
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 5 секунд |
Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от вершины S до вершины F.
Формат входных данных
В первой строке входного файла три числа: N, S и F (1 <= N <= 100;
1 <= S, F <= N), где N - количество вершин графа.
В следующих N строках записаны по N чисел - матрица
смежности графа, где число в i-ой строке j-ом столбце соответствует
ребру из i в j: -1 означает отсутствие ребра между вершинами,
а любое неотрицательное число - наличее ребра данного веса.
На главной диагонали матрицы всегда записаны нули.
Формат выходных данных
Вывести искомое расстояние или -1, если пути между указанными
вершинами не существует.
Пример
| input.txt | output.txt |
3 1 2 0 -1 2 3 0 -1 -1 4 0 |
6 |