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