Problem
Kenarlarına bazı negatif olmayan ağırlıklar (uzunluklar) atanan yönlendirilmiş bir grafik verildi. Aralarındaki en kısa yolun en fazla uzunluğa sahip olduğu iki köşe bulmamız gerekiyor.
Giriş
İlk satır, N ≤50 köşe sayısını içerir. Daha sonra grafiğin bitişiklik matrisi gelir, yani her biri N sayı içeren N satır. Bitişiklik matrisinin i'nci satırındaki j'inci sayı, i'inci tepe noktasından j'inci köşeye giden kenarın uzunluğunu belirtir. Uzunluklar 0 ile 1000000 arasında herhangi bir değer alabilir. Matrisin ana köşegeninde sıfır olması garanti edilir.
Çıktı
Tek bir sayı yazdır – istenen yolun uzunluğu.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
3
0 7 3
7 0 10
2 215 0
|
10
|