题解

思路

一条路线走到当前城市时，今后最有利的表演地点只取决于沿途见过的最大 $w$。因此将“当前城市”和“最大收入城市”组成状态。

做法

状态 $(u,k)$ 表示当前在 $u$，沿途最大单次收入为 $w_k$。对每个状态保存字典序最优的二元组：已经表演的次数最少；次数相同时手中钱最多。

尝试价格为 $c$ 的航班时，若当前钱不足，就在城市 $k$ 补做

场表演，然后支付 $c$。到达新城市后，如果它的 $w$ 更大，就更新 $k$。用优先队列按表演次数从小到大扩展状态；相同次数优先保留更多钱。每个状态只需保留这一对最优值，因为表演更少或同次数钱更多一定不会更差。

小规模可以枚举状态路径。所有 $w_i$ 相同时，表演地点无区别，只需求从 $1$ 到 $n$ 的最短总票价，再计算弥补资金缺口的表演次数。

复杂度

状态数为 $O(n^2)$，总转移数为 $O(nm)$，使用优先队列后时间复杂度为 $O(nm\log n)$，空间复杂度为 $O(n^2+m)$。