Гениальная прогулка

Задачу можно решить используя модификацию алгоритма Дейкстры. Заметим, что для каждой вершины нас, как и в алгоритме Дейкстры, интересует лишь минимальный момент времени, в который в неё можно прийти. И при этом, для каждого ребра $$$i$$$ из $$$u_i$$$ в $$$v_i$$$ можно вычислить минимальный момент времени, в который можно закончить переход по нему и оказаться в $$$v_i$$$, если минимальный момент времени, в который можно оказаться в $$$u_i$$$ это $$$x$$$. Если $$$a_i < d_i$$$, по ребру пройти невозможно. Иначе, если можно начать переход в момент времени $$$x$$$, ответом является $$$x + d_i$$$. Иначе, нужно подождать первого момента, когда дождь закончится, и начать переход. Тогда ответом будет $$$\lceil\frac{x}{a_i + b_i}\rceil \cdot (a_i + b_i) + d_i$$$. Переход по ребру в момент $$$x$$$ можно начать, если выполняется условие $$$x \bmod (a_i + b_i) + d_i \le a_i$$$.