Dijkstra algorithm
Расстояние между вершинами
Коль Дейкстрý писать без кучи,
То тайм-лимит ты получишь...
А в совсем другой задаче
Юзай кучу Фибоначчи!
___________________________________________
Спектакль преподавателей ЛКШ.июль-2007
Дан неориентированный взвешенный граф. Необходимо найти вес минимального пути между двумя вершинами.
Входные данные
Первая строка содержит два натуральных числа n и m (1 ≤ n ≤ 105
, 1 ≤ m ≤ 2 * 105
) - количество вершин и количество рёбер соответственно. Вторая строка содержит натуральные числа s и t (1 ≤ s, t ≤ n, s ≠ t) - номера вершин, длину пути между которыми требуется найти.
Следующие m строк содержат описание рёбер по одному в строке. Ребро номер i описывается тремя целыми числами bi
, ei
и wi
(1 ≤ bi
, ei
≤ n, 0 ≤ wi
≤ 100) - номерами концов ребра и его вес соотвественно.
Выходные данные
Вывести вес минимального пути между вершинами s и t, или -1, если такого пути нет.
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
3