Світлофори#2587

Світлофори

1 секунда

128 мегабайтів

Складна

Кеноша — місто, найближче до Фермера Джона, має $m$ доріг (пронумерованих від $1$ до $m$ ), які з'єднують $n$ перехресть (пронумерованих від $1$ до $n$ ). Жодні дві дороги не з'єднують одну й ту ж пару перехресть, і жодна дорога не з'єднує перехрестя саме з собою. Час подорожі $T_{ij}$ T_{ij} ( $1 \leq T_{ij} \leq 100$ 1 \leq T_{ij} \leq 100) між перехрестями $i$ та $j$ однаковий в обох напрямках (тобто $T_{ij} = T_{j i}$ T_{ij} = T_{ji}).

Кожне перехрестя має світлофор із двома кольорами: синім та фіолетовим. Колір на кожному світлофорі змінюється періодично: спочатку синій певний час, потім фіолетовий інший час. Рух по дорозі між будь-якими двома перехрестями дозволяється почати лише тоді, коли світлофори на обох перехрестях мають однаковий колір у момент відправлення. Кольори світлофорів не обов'язково мають лишатися однаковими під час всієї подорожі дорогою.

Якщо транспортний засіб прибуває на перехрестя у момент зміни світла, він враховує новий колір. Транспортним засобам дозволяється чекати на перехрестях. Дано карту міста, на якій вказано:

Час подорожі $T_{ij}$ T_{ij} для всіх доріг
Тривалість кожного кольору на перехресті $i$ : для синього $D B_{i}$ DB_i ( $1 \leq D B_{i} \leq 100$ 1 \leq DB_i \leq 100), для фіолетового $D P_{i}$ DP_i ( $1 \leq D P_{i} \leq 100$ 1 \leq DP_i \leq 100)
Початковий колір $C_{i}$ C_i світлофора на перехресті $i$ (літера 'B' чи 'P') і залишковий час $R_{i}$ R_i ( $1 \leq R_{i} \leq 100$ 1 \leq R_i \leq 100) до зміни кольору

Знайдіть мінімальний час, необхідний, щоб дістатися зі стартового перехрестя $s$ ( $1 \leq s \leq n$ 1 \leq s \leq n) у пункт призначення $d$ ( $1 \leq d \leq n$ 1 \leq d \leq n, $d \neq = s$ d \neq s).

Розглянемо карту із чотирма перехрестями і п'ятьма дорогами. Фермер Джон хоче доїхати з перехрестя $1$ до перехрестя $4$ . На першому — синій, на решті — фіолетовий.

Мінімальний час — $127$ за маршрутом $1$ - $2$ - $4$ .

Спочатку на першому перехресті світить синій. Оскільки на другому — фіолетовий, транспорт чекає на першому $2$ секунди, а потім їде $4$ секунди на друге.

На $6$ секунді на другому перехресті перемикається синій колір, а на четвертому фіолетовий ще $32$ секунди. Проте, через $32$ секунди на другому перехресті стає фіолетовий, а на четвертому — синій. Відтак треба ще $13$ секунд дочекатися синього на другому, після чого можна їхати $76$ секунд до фінішу ( $4$ ).

Разом: $2 + 4 + 32 + 13 + 76 = 127$ 2 + 4 + 32 + 13 + 76 = 127 секунд.

Нижче зображений графічний план поїздки:

Вхідні дані

Перший рядок містить два цілих числа $s$ і $d$ .

Другий рядок містить два цілих числа $n$ ( $2 \leq n \leq 300$ 2 \leq n \leq 300) та $m$ ( $1 \leq m \leq 14000$ 1 \leq m \leq 14000).

Кожен із наступних $n$ рядків описує перехрестя $i$ символом та трьома цілими числами: $C_{i}$ C_i, $R_{i}$ R_i, $D B_{i}$ DB_i, і $D P_{i}$ DP_i.

Кожен із подальших $m$ рядків описує дорогу $k$ трьома цілими числами: $i$ , $j$ , і $T_{ij}$ T_{ij}.

Вихідні дані

Виведіть мінімальний час проходження шляху із початкового перехрестя до пункту призначення. Якщо шлях неможливий — виведіть $0$ .

Приклади

Приклад 1