Svetoforlar
Kenoşa - Fermer Conun yaxınlığında yerləşən şəhərdir və burada n kəsişmə nöqtəsini (1..n nömrələnmiş) birləşdirən m yol (1..m nömrələnmiş) mövcuddur. Heç bir iki yol eyni kəsişmə nöqtəsi cütünü birləşdirmir və heç bir yol kəsişmə nöqtəsini öz-özünə birləşdirmir. Kəsişmə nöqtələri i və j arasında səyahət vaxtı T[ij] (1 ≤ T[ij] ≤ 100) hər iki istiqamətdə eynidir (yəni T[ij] = T[ji]).
Hər bir kəsişmə nöqtəsində iki rəngli işıqfor var: mavi və bənövşəyi. İşıqlar dövri olaraq dəyişir: bir müddət mavi, sonra isə bənövşəyi olur. İki kəsişmə nöqtəsi arasında yola çıxmaq yalnız hər iki kəsişmə nöqtəsindəki işıqforların işıqları eyni rəngdə olduğu zaman mümkündür. İşıqforların rəngləri yol boyu eyni qalmalı deyil.
Əgər nəqliyyat vasitəsi işıq dəyişmə anında kəsişmə nöqtəsinə çatarsa, o, yeni işıq rənglərini nəzərə almalıdır. Nəqliyyat vasitələrinə kəsişmə nöqtələrində gözləməyə icazə verilir. Sizə şəhərin xəritəsi təqdim olunur ki, bu da göstərir:
Bütün yollar üçün səyahət vaxtı
T[ij]Kəsişmə nöqtəsində i hər iki rəngin müddəti: mavi rəng üçün
DB[i](1 ≤DB[i]≤ 100) və bənövşəyi rəng üçünDP[i](1 ≤DP[i]≤ 100)Kəsişmə nöqtəsində i işıqforun başlanğıc rəngi
C[i](müvafiq olaraq 'B' və ya 'P' hərfi) və rəngin dəyişməsinə qalan vaxtR[i](1 ≤R[i]≤ 100)
Kəsişmə nöqtəsindən s (1 ≤ s ≤ n) kəsişmə nöqtəsinə d (1 ≤ d ≤ n, d ≠ s) ən qısa müddətdə necə çatmaq olar?
Dörd kəsişmə nöqtəsi və beş yol olan xəritəni nəzərdən keçirək. Fermer Con kəsişmə nöqtəsindən 1 kəsişmə nöqtəsinə 4 çatmaq istəyir. Birinci kəsişmə nöqtəsində rəng mavidir, qalanlarında isə bənövşəyi.
Ən qısa vaxt 127-dir, 1-2-4 yolunu istifadə edərək.
Əvvəlcə, kəsişmə nöqtəsində 1 işıq mavidir. Kəsişmə nöqtəsində 2 işıq bənövşəyi olduğundan, nəqliyyat vasitəsi 1 kəsişmə nöqtəsində 2 saniyə gözləyir, sonra 2 kəsişmə nöqtəsinə 4 saniyə səyahət edir.
6-cı saniyədə, kəsişmə nöqtəsində 2 işıq mavi olur, halbuki kəsişmə nöqtəsində 4 işıq mavi olmaq üçün daha 32 saniyə var. Lakin, 32 saniyədən sonra, kəsişmə nöqtəsində 2 işıq bənövşəyi olur və kəsişmə nöqtəsində 4 işıq eyni vaxtda mavi olur. Beləliklə, nəqliyyat vasitəsi 2 kəsişmə nöqtəsində işığın mavi olması üçün daha 13 saniyə gözləməlidir, sonra işıqlar eyni rəngdə olur və nəqliyyat vasitəsi 76 saniyə ərzində təyinat kəsişmə nöqtəsinə 4 səyahət edir.
Ümumi vaxt 2 + 4 + 32 + 13 + 76 = 127 saniyədir.
Aşağıda səyahət planı göstərilmişdir:
Giriş məlumatları
Birinci sətir iki tam ədəd s və d ehtiva edir.
İkinci sətir iki tam ədəd n (2 ≤ n ≤ 300) və m (1 ≤ m ≤ 14000) ehtiva edir.
Növbəti n sətirdən hər biri kəsişmə nöqtəsini i simvolu və üç tam ədəd ilə təsvir edir: C[i], R[i], DB[i] və DP[i].
Növbəti m sətirdən hər biri yolu k üç tam ədəd ilə təsvir edir: i, j və T[ij].
Çıxış məlumatları
Mənbə kəsişmə nöqtəsindən təyinat kəsişmə nöqtəsinə minimum vaxtla keçən yolu göstərən vaxtı çap edin. Əgər yol yoxdursa, 0 çıxış edin.