Problem
Negatif olmayan kenar uzunluklarına sahip, yönsüz ağırlıklı bir grafikte belirli bir tepe noktasından diğer tüm tepe noktalarına olan mesafeleri bulan bir program yazın. Programın büyük seyrek grafikler için hızlı olması gerekir.
Giriş
Girişin ilk satırı NUM sayısını içerir — Dijkstra'nın algoritmasının farklı çalıştırma sayısı (farklı grafikler üzerinde). Bunu, her biri aşağıdaki yapıya sahip olan NUM blok takip eder.
Bloğun ilk satırı, boşlukla ayrılmış iki sayı N ve M içerir — grafiğin köşe sayısı ve kenar sayısı. Bunu, her biri boşluklarla ayrılmış üç tamsayı içeren M çizgiler izler. Her biri 0 ile N–1 arasında değişen ilk ikisi karşılık gelen kenarın uçlarını, üçüncü — 0 ile 20000 arasında değişir ve bu kenarın uzunluğunu belirtir. Ayrıca bloğun son satırında 0'dan N–1'e kadar tek bir sayı — zirve, aramanız gereken mesafe.
Bir testteki farklı grafiklerin sayısı NUM, 5'i geçmez. Köşe sayısı 60000'i geçmez, kenarlar — 200000.
Künye
Her biri boşluklarla ayrılmış Ni sayı içeren NUM satırı standart çıktıya (ekran) yazdırın — ağırlıklı yönsüz grafiğin belirtilen başlangıç tepe noktasından 0., 1., 2. vb. noktalarına olan mesafe. köşeler (son sayıdan sonra fazladan bir boşluğa izin verilir). Belirtilen ilk köşeden bazı köşelere ulaşılamıyorsa, mesafe yerine 2009000999 sayısını yazdırın (tüm gerçek mesafelerin daha az olduğu garanti edilir).
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1 |
18 0 5 2 8 |