Формализуем условие. Нам дан взвешенный ориентированный граф. По $$$i$$$-му ребру можно начать идти в момент $$$t$$$, только если существует целое $$$k$$$ такое, что $$$d_i + k \cdot (g_i + p_i) \le t < d_i + k \cdot (g_i + p_i) + g_i$$$. Также существуют запрещённые отрезки времени, в которые в вершине находиться нельзя.

Последнее условие неудобно, поэтому избавимся от него так: разделим каждую вершину на две и будем считать, что первая доступна до $$$l_i$$$ секунды не включительно, а вторая — с $$$r_i + 1$$$ секунды. Тем самым мы сохраним инвариант, что чем раньше мы окажемся в вершине, тем лучше. В этом случае мы можем применить алгоритм Дейкстры. Внутри него, рассматривая очередное ребро $$$(v, u)$$$, посмотрим на минимальное время, за которое мы можем добраться до $$$v$$$, пусть это $$$t$$$. Пусть $$$x = t \mod (g_v+p_v)$$$. Если $$$x < g_v$$$, то начать переход по ребру можно прямо сейчас, иначе нужно ждать начала следующего цикла, то есть $$$(g_v+p_v - x)$$$ секунд. Здесь же нужно учесть, существует ли в момент начала перехода вершина $$$v$$$ и в момент окончания перехода вершина $$$u$$$.

Если до вершины $$$t$$$ (той, что существует до $$$l_t$$$ секунды) можно добраться, пока она жива, то нужно понять, можно ли добраться из неё до любой безопасной вершины, то есть до любой вершины, которая существует, начиная с какого-то момента, а это новые $$$n$$$ вершин, полученных после разделения. Запустим алгоритм Дейкстры второй раз из вершины $$$t$$$ и определим, можно ли добраться до любой такой вершины. Если можно, выведем ответ, иначе выведем максимальное $$$l_i$$$ среди всех вершин, до которых мы можем добраться — это будет время смерти. Отметим, что условие, что с момента последнего перехода до смерти должна пройти хотя бы одна секунда, означает, что если вершина недостижима из-за аномалии в ней, то не нужно пытаться продлить себе жизнь, идя по ребру в неё.

Если же до вершины $$$t$$$ добраться в срок нельзя (или пути вообще нет), то определим, можно ли добраться до безопасной вершины из $$$s$$$, и, аналогично первому случаю, выведем ответ.