e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Məsələlər

Yolların dağıdılması

Yolların dağıdılması

Ölkənin hər bir şəhərlər cütlüyü arasında düz iki istiqamətli yol var. Petr müəyyən sayda yolları elə partlatmaq istəyir ki, heç olmazsa elə iki şəhər olsun ki, onlar arasında gediş olmasın.

Sizə hər bir partlayışın qiyməti məlumdur. Petrin düşündüyünü həyata keçirə bilməsi üçün minimal qiymət tapın.

Giriş verilənləri

Giriş verilənləri bir neçə test ehtiva edir. Hər bir testin ilk sətri ölkədəki şəhərlərin n (n50) sayını ehtiva edir. Növbəti n sətir yolları əks etdirir: i sətrinin j-ci işarəsi i şəhərindən j şəhərinə aparan yolun dağıdılmasının qiymətini verən rəqəmdir.

Çıxış verilənləri

Hər bir test üçün ayrı sətirdə Petrin düşündüyünü həyata keçirməsi üçün minimal qiyməti verməli.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4
0911
9011
1109
1190
6
030900
304120
040174
911021
027207
004170
4
0399
3033
9309
9390
Çıxış verilənləri #1
4
8
9