Ekoloji səyahət#9702
Təəssüf ki, məzuniyyətdə istirahət karbon qazı emissiyasına səbəb olur. CO2 emissiyası keçilən kilometrin dəyərinə görə nəqliyyat növündən asılıdır. Məsələn, qatarla səyahət avtobusla səyahətdən daha ucuz başa gəlir və bu da öz növbəsində avtomobillə səyahətdən daha ucuzdur.
Sizin məqsədiniz evinizdən, koordinatları (x[s], y[s]) olan nöqtədən, təyinat nöqtəsinə, koordinatları (x[d], y[d]) olan nöqtəyə səyahəti planlaşdırmaqdır. Səyahətin ətraf mühitə təsirini nəzərə alaraq, məzuniyyət zamanı CO2 emissiya xərclərini minimuma endirmək istəyirsiniz, lakin ümumi keçilən kilometr sayını müəyyən edilmiş büdcə B çərçivəsində saxlamaq istəyirsiniz.
Planlaşdırmaya kömək etmək üçün, sizdə n stansiyadan ibarət xəritə var, bəlkə də t müxtəlif nəqliyyat növləri (təyyarə, qatar və s.) ilə əlaqələndirilmişdir, 1, ... , t ilə nömrələnmişdir. Hər bir nəqliyyat növünün məsafə üzrə CO2 dəyəri c[1], ..., c[t] ilə ölçülür. Siz evinizdən təyinat nöqtəsinə, evinizdən istənilən stansiyaya və istənilən stansiyadan təyinat nöqtəsinə avtomobillə c[0] məsafə vahidi qiymətinə səyahət edə bilərsiniz. c[0] həmişə c[1], ..., c[t]-dən böyükdür.
Hər bir n stansiyası koordinatlara malikdir (x[i], y[i]) üçün i = 0, ..., n - 1. Hər bir stansiya digər stansiyalarla bir və ya bir neçə nəqliyyat növü t vasitəsilə əlaqələndirilə bilər. Hər bir əlaqə iki tərəflidir, buna görə də yalnız bir istiqamət göstərmək lazımdır. İki stansiya arasında bir neçə nəqliyyat növü ola bilər. Siz iki stansiya arasında yalnız onların əlaqələri vasitəsilə, mövcud nəqliyyat növlərindən istifadə edərək hərəkət edə bilərsiniz (stansiyalar arasında avtomobillə hərəkət qadağandır).
İki nöqtə a və b arasındakı məsafə, (x[a], y[a]) və (x[b], y[b]) arasındakı müstəvi məsafəsidir, yuxarıya doğru ən yaxın tam ədədə yuvarlaqlaşdırılır:
və a və b arasında i növ nəqliyyat vasitəsilə keçid zamanı CO2 dəyəri:
cost(a, b, i) = c[i] * dist(a, b)
Mənbə və təyinat nöqtəsi koordinatları, büdcə B, məsafə vahidləri ilə ifadə olunan, nəqliyyat növlərinin siyahısı və onların müvafiq CO2 emissiya xərcləri, həmçinin stansiyalar şəbəkəsi verildikdə, sizin vəzifəniz səyahət zamanı B kilometrdən çox olmayan minimal mümkün CO2 emissiya xərclərini hesablamaqdır.
Aşağıdakı sətirlərdən ibarətdir:
Sətir 1 iki tam ədəd, boşluqla ayrılmış, x[s] və y[s], evinizin koordinatları.
Sətir 2 iki tam ədəd, boşluqla ayrılmış, x[d] və y[d], təyinat nöqtənizin koordinatları.
Sətir 3 tam ədəd B (0 ≤ B ≤ 100), maksimum məsafə (kilometrlərlə), razılaşdığınız məsafə.
Sətir 4 tam ədəd c[0], avtomobillə keçid zamanı məsafə vahidi başına CO2 dəyəri.
Sətir 5 tam ədəd t (1 ≤ t ≤ 100), nəqliyyat növlərinin sayı (avtomobillərdən başqa).
Sətir i + 5, üçün 1 ≤ i ≤ t, tam ədəd c[i], nəqliyyat növü i üçün məsafə vahidi başına CO2 dəyəri (1 ≤ c[1], ..., c[t] < c[0] ≤ 100).
Sətir t + 6 tam ədəd n (1 ≤ n ≤ 1000), stansiyaların sayı.
Sətir i + t + 7 stansiya i-ni (0 ≤ i < n) təsvir edir və 3 + 2 * l[i] tam ədədlərdən ibarətdir, boşluqla ayrılmış. İlk üç tam ədəd x[i], y[i] və l[i]-dir. Cütlük (x[i], y[i]) stansiya i-nin koordinatlarını, l[i] isə stansiya i ilə digər stansiyalar arasında əlaqələrin sayını təmsil edir. Qalan l[i] cüt tam ədədlər (j, m[j]) stansiya j (0 ≤ j < n) ilə m[j] nəqliyyat növü (1 ≤ m[j] ≤ t) vasitəsilə əlaqəni təsvir edir. Bütün əlaqələr iki tərəflidir.
Bütün giriş məlumatları tam ədədlərdir. Bütün koordinatlar [0, 100] * [0, 100] sahəsinə aiddir. Hər bir stansiyanın digər stansiyalarla ən çox 100 əlaqəsi var.
Bir tam ədəd çıxarın, minimal mümkün CO2 emissiya xərclərini təmsil edən, və ya -1, əgər məsafə çərçivəsində qəbul edilə bilən dəyər yoxdursa.
Nəticələr aşağıdakı marşrut üzrə CO2 dəyərinə uyğundur:
evdən (1, 1) stansiya 0-a (2, 3) avtomobillə 100 * sqrt(1^2 + 2^2) = 300 qiymətinə,
stansiya 2-yə (9, 3) nəqliyyat növü 2 ilə 50 * sqrt(7^2 + 0^2) = 350 qiymətinə,
təyinat nöqtəsinə (10, 2) avtomobillə 100 * sqrt(1^2 + 1^2) = 200 qiymətinə. Ümumi məbləğ 850.
Bu marşrut etibarlıdır, çünki ümumi keçilən məsafə 3 + 7 + 2 = 12 büdcə 12 daxilindədir.
Nümunə 1