Məmurlar və yollar#11146
Şəhər Flovildə məmurun seçkiləri keçirilir. Şəhər zirvə və kənardan ibarət olan əlaqəli istiqamətsiz qrafla təsvir olunur. Hər bir kənar üç ədəd ilə verilir: u_i, v_i, len_i (burada u_i və v_i zirvələr arasında kənardır) və len_i kənarın uzunluğunu göstərir.
Hər məmura yaşayış yeri təqdim olunur. Nömrəsi olan məmur qrafın h_t nömrəli zirvəsində yaşayır. Şəhərdə məmurların işləri üçün boş ofis var. Nömrəsi olan məmur qrafın w_t nömrəli zirvəsində ofis seçərsə, hər gün h_t zirvəsindən w_t zirvəsinə ən qısa yolla avtomobillə gedəcək. Məmur mövcud olan bütün ən qısa yollar arasından marşrutu belə seçir: marşrutun zirvə nömrələrini tərsinə düzərək (yəni iş yerindən evə doğru) "leksikoqrafik olaraq ən kiçik" yolu seçir.
Məsələn, əgər 0 zirvəsindən 5 zirvəsinə 2 ən qısa yol varsa: 0→1→2→4→5 və 0→3→5, məmur 0→3→5 yolunu seçəcək. Çünki tərsinə (iş yerindən evə doğru): 5→4→2→1→0 və 5→3→0. "Leksikoqrafik olaraq ən kiçik" yol isə 5→3→0-dır.
Məmurun marşrutu boyunca yerləşən bütün yollar (qrafın kənarları) həmişə yaxşı vəziyyətdə saxlanılacaq.
Hər məmur yalnız bir ofis seçməlidir ki, yaxşı vəziyyətdə olan yolların ümumi uzunluğu maksimum olsun.
Birinci sətirdə boşluqla ayrılmış üç tam ədəd , və verilir.
- qrafın zirvələrinin sayı (N \le 100);
- qrafın kənarlarının sayı (M \le 1000);
- məmurların sayı (T \le 8);
Sonra qrafın kənarlarını təsvir edən sətir gəlir. Hər bir kənar formatda verilir: u_i v_i len_i, burada len_i - kənarın uzunluğu (0 \le u_i, v_i \le n), (len_i \le 100000).
Sonra tam ədəd olan sətir gəlir:
0 \le h_1, h_2, …, h_t, …, h_T \le n - məmurların evlərinin yerləşdiyi zirvələrin nömrələri;
Sonra tam ədəd olan sətir gəlir:
0 \le w_1, w_2, …, w_t, …, w_T \le n - məmurların gələcək iş yerlərinin yerləşdiyi zirvələrin nömrələri.
- zəmanətli təmir olunacaq yolların maksimum ümumi uzunluğu.
0 \le w_{res,1}, w_{res,2}, …, w_{res,t}, …, w_{res,T} \le n - zəmanətli təmir olunacaq yolların maksimum ümumi uzunluğuna uyğun gələn məmurların gələcək iş yerlərinin yerləşdiyi zirvələrin nömrələri.
Nümunə 1
Nümunə 10
Nümunə 11
Nümunə 12