АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Соревнования
Новости Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

778. Дейкстра

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

 
Задача "Дейкстра"

Дан ориентированный взвешенный граф. Для него вам необходимо найти 
кратчайшее расстояние от одной заданной вершины до другой.

Входные данные:
В первой строке входного файла три числа: N, S и F (1 <= N <= 100; 
1 <= S, F <= N), где N - количество вершин графа, S - начальная 
вершина, а F - конечная. В следующих N строках по N чисел - матрица 
смежности графа, где число в i-ой строке j-ом столбце соответствует
ребру из i в j: -1 означает отсутствие ребра между вершинами, 
а любое неотрицательное число - присутствие ребра данного веса. 
На главной диагонали матрицы - всегда нули.

Выходные данные:
Вывести искомое расстояние или -1, если пути между указанными 
вершинами не существует.

Пример входного файла:
3 1 2
0 -1 2
3 0 -1
-1 4 0

Пример выходного файла:
6


Описание алгоритма Дейкстры.

Храним массив кратчайших уже найденных путей до каждой из вершин.
Вначале расстояние до начального элемента - 0, до остальных - бесконечность

N раз повторяем шаг алгоритма:
1) Находим вершину, из которой мы еще не ходили, и в расстояние до которой
минимально
2) Ходим из этой вершины, т.е.:
-Проверяем, если расстояние до данной вершины + ребро из нее в какую-то другую
вершину меньше, чем расстояние до той вершины, уменьшаем расстояние до
той вершины
-Помечаем, что мы походили из этой вершины.

После окончания мы получим массив кратчайших путей.

Статистика Послать на проверку Обсуждение задачи Автор/источник: olympiads.ru
Учебные курсы / Задачи с olympiads.ru /
776. 249 - Шифровка 2 778. 779. 253 - Заправки 780. 254 - Заправки-2 781. 255 - Автобусы
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.