本题解是官方题解的 AI 中文翻译。

子任务 1. 如果所有 $w_i = 1$，那么答案就是最短路长度减去 $p$，可以用 Dijkstra 算法在 $O(m \log n)$ 内找到。

子任务 4. 如果所有 $s_i \leq 100$，可以设计状态 $dp[v][ans] = \text{最大剩余金钱}$，转移方式类似 Dijkstra 算法。注意到答案不会超过 $S \cdot n$，其中 $S = \max s_i$。因此总复杂度为 $O(S \cdot n \cdot (n + m) \cdot \log n)$。

子任务 2. 注意表演可以“延后”进行。当我们钱不够过某条边时，可以在已经经过的顶点中提前多次表演，以获取最多的钱。如果图是一个两端分别为 $1$ 和 $n$ 的链（bamboo），只需在前缀中维护 $w_i$ 最大的顶点，每当钱不够时就在该顶点表演。这样复杂度为 $O(n)$。

完整解法. 借鉴子任务 2 的思路，可以设计状态 $dp[v][best] = (\textit{最少表演次数}, \textit{最大剩余金钱})$，其中 $v$ 表示当前所在顶点，$best$ 表示已经经过的、$w_i$ 最大的顶点。可以证明，最优策略是先最小化表演次数，再最大化剩余金钱。该动态规划的转移方式与子任务 4 类似，总复杂度为 $\mathcal{O}(mn \log n)$。