e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

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 nm (1n105, 1m2 * 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 st (1s, tn, st) 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, eiwi (1bi, ein, 0wi100) ədədləri ilə ifadə olunur.

Çıxış verilənləri

Çıxış faylının yeganə sətri st 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.

prb625.gif

Zaman məhdudiyyəti 4 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 4
1 3
1 2 1
2 3 2
3 4 5
4 1 4
Çıxış verilənləri #1
3