e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Dijkstra algorithm

Расстояние между вершинами

Коль Дейкстрý писать без кучи,

То тайм-лимит ты получишь...

А в совсем другой задаче

Юзай кучу Фибоначчи!

___________________________________________

Спектакль преподавателей ЛКШ.июль-2007

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

Входные данные

Первая строка содержит два натуральных числа n и m (1n105, 1m2 * 105) - количество вершин и количество рёбер соответственно. Вторая строка содержит натуральные числа s и t (1s, tn, st) - номера вершин, длину пути между которыми требуется найти.

Следующие m строк содержат описание рёбер по одному в строке. Ребро номер i описывается тремя целыми числами bi, ei и wi (1bi, ein, 0wi100) - номерами концов ребра и его вес соотвественно.

Выходные данные

Вывести вес минимального пути между вершинами s и t, или -1, если такого пути нет.

prb625.gif

Лимит времени 4 секунды
Лимит использования памяти 128 MiB
Входные данные #1
4 4
1 3
1 2 1
2 3 2
3 4 5
4 1 4
Выходные данные #1
3