Yaxşı Oyun Necə Yaradılır#3549
Bir video oyun şirkəti olan ICPC (International Company for Playing and Competing) yeni bir arcade oyunu üzərində işləyir. Bu oyun, oyunçuların bacarıqlarına uyğun fərqli yollar seçə biləcəyi çoxlu budaqlara malikdir. Yeni başlayanlar asan yollarla oyundan zövq ala bilər, təcrübəli oyunçular isə yüksək xal toplamaq üçün çətin yolları seçə bilərlər.
Oyunda bir çox yoxlama nöqtəsi var və bu nöqtələr yollarla birləşdirilir. Hər yol bir neçə mərhələdən ibarətdir və bir yoldakı mərhələləri tamamladıqda oyunçular növbəti yoxlama nöqtəsinə keçirlər. Oyun, oyunçular müəyyən bir yoxlama nöqtəsinə çatdıqda sona çatır. Bəzi yoxlama nöqtələrində oyunçular hansı yolla gedəcəklərini seçə bilərlər, beləliklə yollar ayrılır. Bəzən müxtəlif yollar bir yoxlama nöqtəsində birləşir. Yoxlama nöqtələri arasındakı yollar istiqamətlidir və döngə yoxdur (əks halda, oyunçular oyunu sonsuza qədər oynaya bilər). Başqa sözlə, oyunun strukturu yoxlama nöqtələri arasındakı yolları istiqamətli kənar kimi nəzərə alaraq DAG (istiqamətli döngəsiz qraf) kimi qəbul edilə bilər.
İnkişaf qrupu oyunun beta versiyasını tamamladı və digər qruplardan rəy aldı. Rəylər ümumilikdə müsbət idi, lakin bəzi testçilər bəzi yolların çox qısa olduğunu qeyd etdilər. Həqiqətən də, beta versiyada bir oyunda mərhələlərin sayı yolların uzunluğuna görə kəskin şəkildə dəyişə bilər. Oyun dizaynerləri sıx inkişaf cədvəli səbəbindən beta versiyada bir çox parlaq ideyalarının istifadə edilmədiyindən şikayət etdilər. Onlar final məhsulda daha çox mərhələnin daxil edilməsini istəyirdilər.
Lakin, daha çox mərhələ əlavə etmək asan deyil. Bu bir arcade oyunudur – əgər oyun vaxtı çox uzun olarsa, bu, oyunun gəlirini azaldar və arcade sahibləri şikayət edərdilər. Beləliklə, final məhsulun ən uzun yolu beta versiyasından daha uzun ola bilməz. Üstəlik, oyunun prodüseri yolların strukturunu dəyişdirmək istəmirdi (yəni, yoxlama nöqtələrinin bir-birinə necə bağlandığını), çünki bu, ssenarinin yenidən yazılmasını, səslərin yazılmasını, yeni kəsik səhnələrin yaradılmasını və s. tələb edərdi.
Bütün bunları nəzərə alaraq, prodüser maksimum mümkün mərhələ sayını bir oyunda saxlayaraq və yolların strukturunu dəyişmədən mümkün qədər çox yeni mərhələ əlavə etməyə qərar verdi. Oyuna neçə yeni mərhələ əlavə edilə bilər?
Girişin ilk sətri iki müsbət tam ədəd N və M (2 ≤ N ≤ 100, 1 ≤ M ≤ 1000) ehtiva edir. N oyunun açılışı və sonu daxil olmaqla yoxlama nöqtələrinin sayını göstərir. M yoxlama nöqtələri arasındakı yolların sayını göstərir.
Növbəti M sətir oyunun beta versiyasındakı yolların strukturunu təsvir edir. i-ci sətir üç tam ədəd x_i, y_i və s_i (0 ≤ x_i < y_i ≤ N-1, 1 ≤ s_i ≤ 1000) ehtiva edir, bu da x_i yoxlama nöqtəsindən y_i yoxlama nöqtəsinə gedən və s_i mərhələdən ibarət olan bir yol olduğunu təsvir edir. Yoxlama nöqtələrinin indeksləri üçün qeyd edin ki, 0 oyunun açılışını və N-1 oyunun sonunu göstərir. Hər bir yoxlama nöqtəsi i üçün açılışdan sona qədər keçən və yoxlama nöqtəsi i-dən keçən bir yolun mövcud olduğunu qəbul edə bilərsiniz. Həmçinin, eyni yoxlama nöqtələri cütünü birləşdirən iki yolun olmadığını qəbul edə bilərsiniz.
Aşağıdakı məhdudiyyətlər altında oyuna əlavə edilə biləcək maksimum yeni mərhələ sayını ehtiva edən bir sətir çıxarın:
Bir oyunda mümkün olan maksimum mərhələ sayını artıra bilməzsiniz (yəni, sona qədər olan ən uzun yolun uzunluğu).
Yolların strukturunu dəyişə bilməzsiniz (yəni, yoxlama nöqtələrinin bir-birinə necə bağlandığını).
Beta versiyada artıq mövcud olan heç bir mərhələni silə bilməzsiniz.
Nümunə 1