| Codeforces Round 766 (Div. 2) |
|---|
| Закончено |
Майора Рама преследует его заклятый враг Рагхав. Рам должен добраться до вершины здания, чтобы сбежать на вертолете, однако здание горит. Рам должен выбрать оптимальный путь, чтобы добраться до вершины здания, потеряв минимальное количество здоровья.
Здание состоит из $$$n$$$ этажей, на каждом этаже $$$m$$$ комнат. За $$$(i, j)$$$ обозначим $$$j$$$-ю комнату на $$$i$$$-м этаже. В здании $$$k$$$ лестниц. $$$i$$$-я лестница позволяет Раму подняться из комнаты $$$(a_i, b_i)$$$ в $$$(c_i, d_i)$$$, но не в другом направлении. За проход по $$$i$$$-й лестнице Рам получает $$$h_i$$$ очков здоровья. Гарантируется, что для всех лестниц $$$a_i < c_i$$$.
Если Рам находится на $$$i$$$-м этаже, то он может двигаться влево или вправо. Путешествовать по этажам, однако, сложно, поэтому если Рам переходит от комнаты $$$(i, j)$$$ к $$$(i, k)$$$, он теряет $$$|j-k| \cdot x_i$$$ очков здоровья.
Изначально Рам находится в комнате $$$(1, 1)$$$, а вертолет ожидает его в $$$(n, m)$$$. Какое минимальное количество очков здоровья Рам может потерять, если выберет оптимальный путь? Обратите внимание, что этот ответ может быть отрицательным (в этом случае он наберет очки здоровья). Выведите «NO ESCAPE», если Рам никак не может добраться к вертолету.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит $$$3$$$ целых числа $$$n, m, k$$$ ($$$2 \leq n, m \leq 10^5$$$; $$$1 \leq k \leq 10^5$$$) — количество этажей, количество комнат на каждом этаже, и количество лестниц, соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$x_1, x_2, \dots, x_n$$$ ($$$1 \leq x_i \leq 10^6$$$).
Следующие $$$k$$$ строк содержат описания лестниц. Лестница $$$i$$$ описана пятью целыми числами $$$a_i, b_i, c_i, d_i, h_i$$$ ($$$1 \leq a_i < c_i \leq n$$$; $$$1 \leq b_i, d_i \leq m$$$; $$$1 \leq h_i \leq 10^6$$$) — номера комнат, которые она соединяет, и бонус к здоровью при использовании лестницы.
Гарантируется, что для всех лестниц выполняется $$$a_i < c_i$$$, и между любыми двумя комнатами существует не более чем одна лестница.
Гарантируется, что сумма значений $$$n$$$, сумма значений $$$m$$$, сумма значений $$$k$$$ по всем наборам входных данных не превосходят $$$10^5$$$.
Выведите минимальное число очков здоровья, которое Рам может потерять на пути от $$$(1, 1)$$$ до $$$(n, m)$$$. Если Рам не может добраться до вертолета, выведите «NO ESCAPE» (заглавными буквами без кавычек).
45 3 35 17 8 1 41 3 3 3 43 1 5 2 53 2 5 1 66 3 35 17 8 1 4 21 3 3 3 43 1 5 2 53 2 5 1 65 3 15 17 8 1 41 3 5 3 1005 5 53 2 3 7 53 5 4 2 12 2 5 4 54 4 5 2 31 2 4 2 23 3 5 2 4
16 NO ESCAPE -90 27
Рисунок в условии демонстрирует первый пример из условия. Есть только $$$2$$$ возможных пути к $$$(n, m)$$$:
- Рам идет в $$$(1, 3)$$$, поднимается по лестнице в $$$(3, 3)$$$, идет в $$$(3, 2)$$$, поднимается по лестнице в $$$(5, 1)$$$, идет до $$$(5, 3)$$$, откуда улетает на вертолете. Потери здоровья равны $$$$$$ \begin{align*} &\mathrel{\phantom{=}} x_1 \cdot |1-3| - h_1 + x_3 \cdot |3-2| - h_3 + x_5 \cdot |1-3| \\ &= 5 \cdot 2 - 4 + 8 \cdot 1 - 6 + 4 \cdot 2 \\ &= 16. \end{align*} $$$$$$
- Рам идет в $$$(1, 3)$$$, поднимается по лестнице в $$$(3, 3)$$$, идет в $$$(3, 1)$$$, поднимается по лестнице в $$$(5, 2)$$$, идет до $$$(5, 3)$$$ , откуда улетает на вертолете. Потери здоровья равны $$$$$$ \begin{align*} &\mathrel{\phantom{=}} x_1 \cdot |1-3| - h_1 + x_3 \cdot |3-1| - h_2 + a_5 \cdot |2-3| \\ &= 5 \cdot 2 - 4 + 8 \cdot 2 - 5 + 4 \cdot 1 \\ &= 21. \end{align*} $$$$$$
Во втором примере нет пути в $$$(n, m)$$$.
В третьем примере Рам идет в $$$(1, 3)$$$, а затем поднимается по лестнице в $$$(5, 3)$$$. Он теряет $$$5 \cdot 2$$$ очка здоровья и затем получает $$$h_1 = 100$$$ очков. Поэтому его потери равны $$$10-100=-90$$$ (отрицательное число означает, что он улучшил здоровье).
