Dekartçılıq
Dövlət İksivşina N_x şəhərdən ibarətdir və bəzi şəhər cütləri iki tərəfli yollarla birləşdirilib. Hər yolun öz uzunluğu var. İksivşinanın ümumi yollarının sayı M_x-dir və hər bir şəhərdən digərinə yollarla getmək mümkündür. Şəhərlər 1-dən N_x-ə qədər nömrələnib.
Dövlət İgrekivşina N_y şəhərdən ibarətdir və bəzi şəhər cütləri iki tərəfli yollarla birləşdirilib. Hər yolun öz uzunluğu var. İgrekivşinanın ümumi yollarının sayı M_y-dir və hər bir şəhərdən digərinə yollarla getmək mümkündür. Şəhərlər 1-dən N_y-ə qədər nömrələnib.
Dövlət Dekartivşina N=N_x∙N_y şəhərdən ibarətdir. Dekartivşina şəhərləri (x,y) cütləri ilə təmsil olunur, burada x — İksivşina şəhəri, y — İgrekivşina şəhəri. Dekartivşinanın bəzi şəhər cütləri də iki tərəfli yollarla birləşdirilib. Ümumi yolların sayı M=N_x∙M_y+N_y∙M_x-dir. (x_1,y_1) və (x_2,y_2) şəhərləri arasında yol yalnız aşağıdakı hallarda mövcuddur:
Əgər x_1=x_2 və İgrekivşina şəhərləri y_1 və y_2 arasında yol varsa. Bu halda, Dekartivşina şəhərləri (x,y_1) və (x,y_2) arasındakı yolun uzunluğu İgrekivşina şəhərləri y_1 və y_2 arasındakı yolun uzunluğuna bərabərdir.
Əgər y_1=y_2 və İksivşina şəhərləri x_1 və x_2 arasında yol varsa. Bu halda, Dekartivşina şəhərləri (x_1,y) və (x_2,y) arasındakı yolun uzunluğu İksivşina şəhərləri x_1 və x_2 arasındakı yolun uzunluğuna bərabərdir.
Fərqli dövlətlərin şəhərləri arasında yollar yoxdur.
Tapşırıq
Bu məsələ iki alt tapşırıqdan ibarətdir. Hər iki alt tapşırıqda yollarla əlaqə haqqında bütün məlumatlar girişdə verilir.
Birinci alt tapşırıqda, Dekartivşina yolları ilə (1,1) şəhərindən (N_x,N_y) şəhərinə ən qısa yolun uzunluğunu tapmaq lazımdır.
İkinci alt tapşırıqda, Dekartivşinanın bəzi yollarını bağlamaq lazımdır. Sizin vəzifəniz — Dekartivşinada hər hansı bir şəhərdən digərinə getmək üçün ən az ümumi uzunluqda yolları hansı yollardan saxlamaq olar, onu müəyyən etməkdir.
cartesius proqramını yazın ki, bu alt tapşırıqları həll etsin.
Giriş verilənləri
cartesius.dat giriş faylının ilk sətiri həll olunacaq alt tapşırığın nömrəsini (1 və ya 2) ehtiva edir. İkinci sətir N_x və M_x təbii ədədlərini (1≤N_x≤5•10^4, 1≤M_x≤5•10^4) — İksivşina şəhərlərinin və yollarının sayını ehtiva edir. Növbəti M_x sətirlər İksivşina yollarını təsvir edir: hər sətirdə yol ilə birləşdirilmiş müxtəlif şəhərlərin nömrələrini göstərən iki ədəd və müvafiq yolun uzunluğunu göstərən üçüncü ədəd (10^7-dən çox olmayan təbii ədəd) var.
Giriş faylının növbəti sətirində N_y və M_y təbii ədədləri (1≤N_y≤5•10^4, 1≤M_y≤5•10^4) — İgrekivşina şəhərlərinin və yollarının sayını ehtiva edir. Növbəti M_y sətirlər İgrekivşina yollarının təsvirini ehtiva edir; məlumat formatı və məhdudiyyətlər yuxarıda təsvir olunanlarla eynidir.
Çıxış verilənləri
cartesius.sol çıxış faylı alt tapşırığın sualına cavab olaraq tək bir tam ədəd ehtiva etməlidir.
Nümunələr
Qiymətləndirmə
Test dəsti 4 blokdan ibarətdir, bunlar üçün əlavə şərtlər yerinə yetirilir:
12 bal: alt tapşırığın nömrəsi — 1, N_x, M_x, N_y, M_y ədədlərindən heç biri 200-dən çox deyil.
28 bal: alt tapşırığın nömrəsi — 1, əlavə məhdudiyyətlər yoxdur.
12 bal: alt tapşırığın nömrəsi — 2, N_x, M_x, N_y, M_y ədədlərindən heç biri 200-dən çox deyil.
48 bal: alt tapşırığın nömrəsi — 2, əlavə məhdudiyyətlər yoxdur.