Yol Planlayıcısı
Atsiklik yol şəbəkəsi, ümumi N kəsişmədən ibarət olan və hər biri iki kəsişməni (tərtibləri) birləşdirən tək istiqamətli yol seqmentlərindən (kənarlarından) təşkil olunub. Hər bir yol seqmentində səyahət etmək üçün tələb olunan vaxt həmişə müsbətdir və bu vaxt, seqmentdən s istifadə edən avtomobillərin C sayına xətti olaraq bağlıdır:
T(s) = a_S C + b_S
Burada a_S və b_S yol seqmenti s üçün tək dəqiqlikli üzən nöqtə ədədləri kimi ifadə olunan iki sabitdir. Kəsişmədən keçmək üçün tələb olunan vaxt isə 0-dır.
Bu yol şəbəkəsində 0 tərtibindən N-1 tərtibinə bir sıra avtomobillər səyahət etməlidir. Hər bir avtomobil öz səyahət vaxtını azaltmaq üçün öz marşrutunu eqoist şəkildə seçir; hər bir avtomobil bilir ki, digər avtomobillər də öz marşrutlarını eqoist şəkildə seçəcəklər. Sizdən, mənbədən təyinat yerinə qədər olan mümkün yolların hər birində neçə avtomobilin səyahət edəcəyini və bu yollarda səyahət etmək üçün lazım olan vaxtı hesablayan bir proqram yazmağınız xahiş olunur.
Giriş verilənləri
Giriş faylı bir neçə testdən ibarətdir və aşağıdakı kimi təşkil olunub. Birinci sətir testlərin sayını ehtiva edir. Sonrakı sətirlər testlərin spesifikasiyasını ehtiva edir. Hər bir testin birinci sətirində boşluqlarla ayrılmış şəkildə tərtiblərin sayı, kənarların sayı və avtomobillərin sayı verilir. Daha sonra hər bir kənar ayrıca sətirdə verilir və boşluqlarla ayrılmış şəkildə aşağıdakı sahələri ehtiva edir: mənbə tərtibi, təyinat tərtibi, a_S və b_S.
Çıxış verilənləri
Çıxış hər bir test girişi üçün şəbəkədə hər hansı bir avtomobilin səyahət etməsi üçün minimum vaxtı, aşağıya doğru ən yaxın tam ədədə yuvarlaqlaşdırılmış şəkildə bir sətir ehtiva edəcək.
Qeyd: Birinci giriş 4 tərtib və 4 kənardan ibarətdir; 4000 avtomobil 0 tərtibindən 3 tərtibinə səyahət etməlidir. Ən kiçik səyahət vaxtına nail olmaq üçün avtomobillər iki mümkün yoldan (0-1-3) və (0-2-3) birini seçəcək, belə ki, hər ikisində avtomobillərin sayı bərabər olacaq; beləliklə minimum səyahət vaxtı aşağı (0.01 * 2000 + 45.1) = 65-dir.
İkinci giriş birinciyə bənzəyir, lakin 1 və 2 tərtibləri arasında sıfır xərcli bir kənar əlavə olunur. Bu halda, bütün avtomobillər eqoist şəkildə (0-1-2-3) yolunu seçir və minimum səyahət vaxtı 80-dir.