首先不考虑 w（每条边的难度）的数据范围，我们可以得到以下的做法。 预处理: 用 spfa 求出 dis[i]，表示：从 x 到每一个点的路径上，最大难度的最小值 用 addp[i] （一个 vector）存储：牛半仙的困难接受程度从 i-1 增加到 i 的时候，他能见到的新的妹子们。将 i 号节点 push 到 addp[dis[i]] 里。 计算一个 ans 数组，其 ans[i] 表示：在牛半仙的困难接受程度为 i 的时候，他一次出行能见到几种妹子开一个桶，i 从 0 扫到 W_max，每一次将 addp[i] 中的节点加到桶中，看是否是新增的类别 预处理一下前缀和，...