题解

思路

对一条路径的边权多重集，前 $k$ 大元素之和可以写成

$$\min_{0\le x\le 1000}\left(kx+\sum_{e\text{ 在路径上}}\max(w_e-x,0)\right).$$

固定阈值 $x$ 后，把每条边的权值改成 $\max(w_e-x,0)$，括号中的路径部分就变成普通非负边权路径和。

子任务 1

图很小且无环，可以深度优先搜索枚举从 $1$ 到 $n$ 的所有路径，维护路径上最大的至多 $k$ 个边权。收集全部路径长度后排序即可。

子任务 2

若所有边权都等于 $w$，一条含 $L$ 条边的路径长度为 $w\min(L,k)$。因此先在单位边权图上求第二短的路径边数 $L_2$，答案就是 $w\min(L_2,k)$。

做法

阈值表达式在相邻两个输入边权之间是线性函数，最小值一定在端点取得。因此只需枚举 $x=0$ 和输入中实际出现的不同边权。在变换后的非负边权图上，用优先队列按距离从小到大扩展路径；每个顶点只接受前两次出队，从而取得该阈值下到达顶点 $n$ 的前两条路径。零权边与等长路径也会作为不同的路径条目被保留。

设原问题的第二条路径为 $P$，取使上式在 $P$ 上达到最小值的阈值 $x$。如果在该阈值下有两条其他路径排在 $P$ 前面，那么它们在原定义下的长度也都不大于 $P$；其中某条路径已经能作为原问题的第二条路径。因此，某个正确的第二路径一定出现在所有阈值前两条路径的并集中。

注意，阈值表达式对一条候选路径可能大于它按原定义计算的长度，不能直接使用变换后的距离。我们按边编号保存并去重所有候选路径，再对每条候选路径重新选出最大的 $k$ 条边求和。把这些真实长度排序，第二个值就是答案。

若所有阈值下都不存在第二条路径，则输出 $-1$。

复杂度

设不同边权数为 $D$，则每组数据枚举至多 $D+1\le1001$ 个阈值。每个阈值中每个顶点最多出队两次，时间复杂度为 $O(Dm\log m)$，空间复杂度为 $O(n+m)$。