Problem
Yönlendirilmiş ağırlıklı asiklik bir grafik verilmiştir. İçindeki en kısa yolu bulmak gerekiyor
s köşe noktasından t köşe noktasına.
Giriş:
Girdi dosyasının ilk satırı dört tam sayı n, m, s ve t içerir - sırasıyla köşelerin sayısı, grafiğin kenarları, ilk ve son köşeler (1 <= n < 100000; 0 <= m <= 200000;1
s, t <= n).
Sonraki m satır, her satırda bir tane olacak şekilde kenarların açıklamalarını içerir.
Kenar sayısı i, üç tamsayı b
i, e
i ve w
i ile tanımlanır - sırasıyla kenarın başlangıcı, sonu ve uzunluğu ( 1 <= b
i, e
i <= n;|w
i| <= 1000).
Grafik, döngüler ve döngüler içermez.
Çıktı:
Çıktı dosyasının ilk satırı tek bir tamsayı içermelidir - s'den t'ye en kısa yolun uzunluğu.
s'den t'ye giden bir yol yoksa "Ulaşılamaz" yazdırın.
Örnekler:
| Giriş |
Çıktı |
2 1 1 2
1 2 -10
| -10 |
2 1 2 1
1 2 -10
| Ulaşılamaz |