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ə

Çəkili qraf verilib. İki təpə arasındakı minimal yolun çəkisini tapmalı.

Giriş verilənləri

İlk sətirdə qrafın uyğun olaraq təpələrinin və tillərinin sayını ifadə edən iki natural nm (n1000, m10000) ədədləri verilir. İkinci sətirdə aralarındakı məsafənin tapılması tələb olunan təpələrin nömrəsini ifadə edən iki natural st (s, tn, st) ədədələri verilir. Növbəti m sətrin hər biri tili ifadə edir. i nömrəli sətir uyğun olaraq tilin birləşdirdiyi təpə nöqtələri və çəkisini ifadə edən üç natural ədəd ilə: bi, eiwi (bi, ein, 0wi105) ifadə olunub. s-dən t-yə yolun olduğuna zəmanət verilir.

Çıxış verilənləri

Yeganə sətirdə st təpələri arasındakı minimal yolun çəkisini ifadə edən natural ədədi verməli.

Zaman məhdudiyyəti 1 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
Mənbə 2018 Azerbaijan School Competition, II Stage, April 8, Problem A