Dijkstra algorithm
Təpələr arasındakı məsafə
Коль Дейкстрý писать без кучи,
То тайм-лимит ты получишь...
А в совсем другой задаче
Юзай кучу Фибоначчи!
___________________________________________
Спектакль преподавателей ЛКШ.июль-2007
İstiqamətlənməmiş çəkili qraf verilir.
İki təpə arasındakı ən qısa yolun çəkisini tapmaq tələb olunur.
Giriş verilənləri
Giriş faylının ilk sətri təpələrin və tillərin sayını ifadə edən iki natural n və m (1 ≤ n ≤ 105
, 1 ≤ m ≤ 2 * 105
) ədədlərini ehtiva edir. Giriş vaylının ikinci sətri aralarındakı uzunluğunu tapmaq tələb olunan təpələrin nömrələrini ifadə edən s və t (1 ≤ s, t ≤ n, s ≠ t) natural ədədlərini ehtiva edir.
Növbəti m sətrin hər biri tillərin təsvirini ehtiva edir. i nömrəli til tilin sonluqlarının nömrələrini və onun çəkisini ifadə edən üç tam bi
, ei
və wi
(1 ≤ bi
, ei
≤ n, 0 ≤ wi
≤ 100) ədədləri ilə ifadə olunur.
Çıxış verilənləri
Çıxış faylının yeganə sətri s və t təpələri arasındakı ən kiçik yolun çəkisini ifadə edən yeganə tam ədədı və ya belə yol mövcud deyilsə -1 ehtiva etməlidir.
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
3