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, s və f (n ≤ 5000, m ≤ 100000, 1 ≤ s, f ≤ n, s ≠ f) 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
, ei
və wi
natural ədədlərini ehtiva edir, uyğun olaraq - i-ci tilin uclarının nömrəsi və onun çəkisi (1 ≤ bi
, ei
≤ n, 0 ≤ wi
≤ 100000).
Çıxış verilənləri
İlk sətirdə bir natural ədəd veilməli - s və f 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.
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