Test Case Dəyişdirilməsi
Siz proqramlaşdırma müsabiqəsinin münsifisiniz və minimum xərc yolunun xərcini tapmaq üçün qraf problemi üçün məlumat dəsti hazırlayırsınız. Bəzi təsadüfi hallar yaratmısınız, lakin onlar maraqlı deyil. İndi cavabı bu ilki rəqəm olan 2010 kimi arzu olunan bir dəyər olan bir məlumat dəsti yaratmaq istəyirsiniz. Bunun üçün bəzi kənarların xərclərini dəyişdirərək minimum xərc yolunun xərcini verilmiş dəyərə uyğunlaşdıracaqsınız. Dəyişikliklərin sayı mümkün qədər az olmalıdır.
Qeyri-mənfi tam ədəd c və yönlü qraf G verilir. G-nin hər bir kənarı qeyri-mənfi tam ədəd xərci ilə əlaqələndirilir. G-də bir düyünündən digərinə bir yol verildikdə, yolu təşkil edən kənarların xərclərinin cəmi kimi yolun xərcini təyin edə bilərik. G-də bir cüt düyün verildikdə, onları birləşdirən yolların xərclərinin minimumu olan qeyri-mənfi bir xərc ilə əlaqələndirə bilərik.
Verilmiş qraf və onun içindəki bir cüt düyün nəzərə alınaraq, sizdən kənarların xərclərini elə tənzimləmək tələb olunur ki, bir düyündən digərinə minimum xərc yolu verilmiş hədəf xərc c olsun. Siz c-nin orijinal qrafda verilmiş düyünlər arasında minimum xərc yolunun xərcindən kiçik olduğunu qəbul edə bilərsiniz.
Məsələn, Şəkil 1-də verilmiş qrafda düyün 1-dən düyün 3-ə yolun minimum xərc 6-dır. Bu minimum xərci 2-yə uyğunlaşdırmaq üçün düyün 1-dən düyün 3-ə kənarın xərcini 2-yə dəyişə bilərik. Bu birbaşa kənar dəyişiklikdən sonra minimum xərc yolu olur.
Başqa bir misalda, Şəkil 2-də verilmiş qrafda düyün 1-dən düyün 12-yə yolun minimum xərc 4022-dir. Bu minimum xərci 2010-a uyğunlaşdırmaq üçün düyün 6-dan düyün 12-yə kənarın və qrafın sağ yarısında olan altı kənardan birinin xərcini dəyişə bilərik. Kənar dəyişikliklərinin bir çox variantı var, lakin dəyişdirilmiş kənarların minimum sayı 2-dir.
Giriş verilənləri
Giriş məlumat dəstlərinin ardıcıllığıdır. Hər bir məlumat dəsti aşağıdakı kimi formatlanmışdır.
n m cf_1 t_1 c_1f_2 t_2 c_2...
f_m t_m c_m
Tam ədədlər n, m və c müvafiq olaraq düyünlərin sayı, kənarların sayı və hədəf xərcdir, hər biri bir boşluqla ayrılmışdır, burada 2 ≤ n ≤ 100, 1 ≤ m ≤ 1000 və 0 ≤ c ≤ 100000.
Qrafdakı hər bir düyün 1-dən n-ə qədər bir tam ədəd ilə təmsil olunur.
Sonrakı m sətir kənarları təmsil edir: tam ədədlər f_i, t_i və c_i (1 ≤ i ≤ m) müvafiq olaraq başlanğıc düyün, təyinat düyünü və i-ci kənarın əlaqəli xərcidir, hər biri bir boşluqla ayrılmışdır. Onlar 1 ≤ f_i, t_i ≤ n və 0 ≤ c_i ≤ 10000 şərtlərini təmin edir. Siz f_i = t_i və (f_i, t_i) = (f_j, t_j) olduqda i = j olduğunu qəbul edə bilərsiniz.
Hər bir məlumat dəsti üçün düyün 1-dən düyün n-ə ən azı bir yol olduğunu və verilmiş qrafın düyün 1-dən düyün n-ə minimum xərc yolunun xərcinin c-dən böyük olduğunu qəbul edə bilərsiniz.
Girişin sonu bir boşluqla ayrılmış üç sıfırdan ibarət bir sətirlə göstərilir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün, düyün 1-dən düyün n-ə minimum xərc yolunun xərcini hədəf xərc c-yə bərabər etmək üçün xərc(ləri) dəyişdirilməli olan minimum kənar sayını ehtiva edən bir sətir çıxarın. Kənarların xərcləri mənfi edilə bilməz. Çıxışda başqa əlavə simvollar olmamalıdır.