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ə

İstiqamətlənməmiş çəkili qraf verilir. İki təpə arasındakı minimal yolun çəkisini tapmalı.

Giriş verilənləri

Giriş faylının ilk sətri n, m, sf (n5000, m100000, 1s, fn, sf) natural ədədlərini ehtiva edir, uyğun olaraq - təpələrin sayı, tillərin sayı, aralarındakı məsafənin tapılması tələb olunan təpələrin nömrələri.

Növbəti m sətir bi, eiwi natural ədədlərini ehtiva edir, uyğun olaraq - i-ci tilin uclarının nömrəsi və onun çəkisi (1bi, ein, 0wi100000).

Çıxış verilənləri

İlk sətirdə bir natural ədəd veilməli - sf təpələri arasındakı minimal yolun çəkisi. İkinci sətirdə isə boşluqla ayrılmış s-dən f-ə gedən ən qısa yoldakı təpələri keçilmə ardicilliğı ilə verməli. Əgər s-dən f-ə yol yoxdursa -1 verməli.

prb625.gif

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
1 2 3