Подгруппа 1. Если все $$$w_i = 1$$$, то ответ это просто длина кратчайшего пути минус $$$p$$$, который можно найти алгоритмом Дейкстры за $$$O(m \log n)$$$.
Подгруппа 4. Если все $$$s_i \leq 100$$$, то можно написать $$$dp[v][ans] = \text{max money}$$$, делая переходы аналогично алгоритму дейкстры. Заметим, что ответ в данном случае не превосходит $$$S \cdot n$$$, где $$$S = \max s_i$$$. Таким, образом алгоритм работает за $$$O(S \cdot n \cdot (n + m) \cdot \log n)$$$
Подгруппа 2. Заметим, что шоу можно делать «отложенно». Как только нам стало не хватать денег, чтобы пройти по ребру, можно сделать несколько шоу заранее среди вершин, которые мы уже прошли, так, чтобы заработать максимальное число денег. Если дан бамбук с концами в $$$1$$$ и $$$n$$$, то достаточно поддерживать вершину с максимальным $$$w_i$$$ на префиксе и делать шоу в ней, если не хватает денег перейти по ребру. Решение в этом случае работает за $$$O(n)$$$
Полное решение. Взяв идею с подгруппы $$$2$$$, можно написать $$$dp[v][best] = (\textit{min show}, \textit{max money})$$$, где $$$v$$$ - номер вершины где мы находимся, а $$$best$$$ - вершина с макс. $$$w_i$$$, через которую мы уже прошли. Можно показать, что оптимально сначала минимизировать $$$w_i$$$, а потом максимизировать количество денег. Эту динамику можно пересчитывать аналогично решению для подгруппы $$$4$$$. Асимптотика $$$\mathcal{O}(mn \log n)$$$