Ən Qısa Yol (Dijkstra)
Çətin
GraphDijkstraPriority Queue
4000 ms
256 MB
n təpə (0..n-1) və m ədəd çəkili, istiqamətsiz kənardan ibarət qraf verilib. src təpəsindən dst təpəsinə ən qısa məsafəni tapın, əlaqə yoxdursa -1 çap edin.
Giriş verilənləri
Birinci sətirdə n və m. Sonrakı m sətirdə hər biri "u v w" (kənar və çəkisi). Son sətirdə "src dst".
Çıxış verilənləri
Ən qısa məsafəni (və ya -1) çap edin.
1Nümunə 1:
Giriş:
5 6
0 1 4
0 2 1
2 1 2
1 3 1
2 3 5
3 4 3
0 4
Çıxış:
7
İzah:0→2(1)→1(2)→3(1)→4(3) = 7
2Nümunə 2:
Giriş:
4 2
0 1 5
2 3 5
0 3
Çıxış:
-1
İzah:0 və 3 arasında əlaqə yoxdur → -1
Məhdudiyyətlər
1 ≤ n ≤ 1000
0 ≤ m ≤ 5000
1 ≤ w ≤ 1000
REDAKTOR
Giriş edin
Kodu yoxlamaq üçün "Göndər" düyməsinə basın
Giriş:
5 6
0 1 4
0 2 1
2 1 2
1 3 1
2 3 5
3 4 3
0 4
Çıxış:
7