Автор задачи: Даниил Орешников, разработчик: Константин Бац
Для решения этой задачи можно воспользоваться системой непересекающихся множеств (disjoint set union, dsu). Будем считать элементами внутри этой системы — миры, а множествами — наборы миров, взаимнодостижимых друг из друга при некотором текущем значении энергетического уровня $$$w_\mathrm{cur}$$$. Это напрямую следует из того, что если в какой-то момент мир становится достижимым, то после мы всегда сможем попасть в этот мир независимо от наших следующих действий, так как энергетический уровень часов не уменьшается. А тогда «достижимая область» всегда представляет из себя некоторый связный подграф исходного графа.
Тогда все, что надо делать — реализовывать «расширение» нашей достижимой области при увеличении энергетического уровня часов, а также увеличивать этот уровень при возможности посетить новые миры. Давайте внутри СНМ хранить множества взаимодостижимых по ребрам веса не больше $$$w_\mathrm{cur}$$$ миров. Помимо этого для каждого мира запомним его хранить характеристику $$$a_i$$$ и в множестве будем поддерживать сумму всех $$$a_i$$$ по элементам множества (достаточно хранить ее отдельным полем в представителе множества).
Заметим, что текущее значение энергетического уровня всегда равно сумме $$$a_i$$$ в множестве, в котором содержится мир с номером $$$s$$$, потому что в соответствующем множестве перед тем, как двигаться за его пределы, мы можем сначала посетить все его вершины и по максимуму увеличить энергетический уровень. Тогда $$$w_\mathrm{cur}$$$ можно найти в СНМ за время $$$\mathcal{O}(\alpha(n))$$$, что можно считать константой. Теперь посмотрим, как достижимых миров меняется:
Таким образом, значение $$$w_\mathrm{cur}$$$ после рассмотрения всех порталов равно значению энергетического уровня часов, то есть ответу на задачу. В таком решении на обработку каждого портала потребуется $$$\mathcal{O}(\alpha(n))$$$ времени, поэтому время работы такого решения — $$$\mathcal{O}(n + m \alpha(n))$$$.