Svetoforlar#2587
Kenoşa, Fermer Conun yaxınlığında yerləşən şəhərdir və burada m yol (1..m nömrələnmiş) n kəsişmə nöqtəsini (1..n nömrələnmiş) birləşdirir. 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 bir 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 kəsişmə nöqtəsinə işığın dəyişdiyi anda ç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, burada göstərilir:
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 üçün DP[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 vaxt R[i] (1 ≤ R[i] ≤ 100)
Kəsişmə nöqtəsindən s (1 ≤ s ≤ n) başlanğıc olaraq d (1 ≤ d ≤ n, d ≠ s) kəsişmə nöqtəsinə ən qısa müddətdə necə çatmaq olar?
Dörd kəsişmə nöqtəsi və beş yol olan xəritədə, Fermer Con 1-ci kəsişmə nöqtəsindən 4-cü kəsişmə nöqtəsinə getmək istəyir. Birinci kəsişmə nöqtəsində rəng mavidir, digər üçündə bənövşəyi.
Ən qısa vaxt 127-dir, 1-2-4 yolundan istifadə olunaraq.
Əvvəlcə 1-ci kəsişmə nöqtəsində işıq mavidir. 2-ci kəsişmə nöqtəsində işıq bənövşəyi olduğuna görə, nəqliyyat vasitəsi 1-ci kəsişmə nöqtəsində 2 saniyə gözləyir və sonra 2-ci kəsişmə nöqtəsinə 4 saniyəyə gedir.
6-cı saniyədə 2-ci kəsişmə nöqtəsində işıq mavi olur, lakin 4-cü kəsişmə nöqtəsində işıq mavi olmaq üçün 32 saniyə qalır. 32 saniyədən sonra isə 2-ci kəsişmə nöqtəsində işıq bənövşəyi, 4-cü kəsişmə nöqtəsində isə mavi olur. Bu halda, nəqliyyat vasitəsi 2-ci kəsişmə nöqtəsində işığın yenidən mavi olması üçün əlavə 13 saniyə gözləməlidir, daha sonra işıqlar uyğun olur və nəqliyyat vasitəsi 76 saniyə ərzində 4-cü kəsişmə nöqtəsinə çatır.
Ümumi vaxt 2 + 4 + 32 + 13 + 76 = 127 saniyədir.
Aşağıda səyahət planının qrafik təsviri verilmişdir:
Birinci sətrdə iki tam ədəd s və d verilir.
İkinci sətrdə iki tam ədəd n (2 ≤ n ≤ 300) və m (1 ≤ m ≤ 14000) verilir.
Sonrakı n sətrin i-cisi kəsişmə nöqtəsi i-ni xarakter və üç tam ədəd ilə təsvir edir: C[i], R[i], DB[i], və DP[i].
Növbəti m sətrin k-sı yol k-yı üç tam ədəd ilə təsvir edir: i, j, və T[ij].
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 çap edin.
Nümunə 1