题意
给定一张连通无向简单图 $G$，每条边有一个边权。
给定正整数 $k$，你需要找到 $G$ 的一条从 $1$ 到 $n$ 的路径，设该路径的长度为 $l$，你需要使得这条路径中边权前 $\min\left{ k, l \right}$ 大的边的边权总和尽可能小。
题解
这种玩意看着人傻了， 一点想法没有， 瞟了下 yhx 的题意下面几行发现好像是减什么东西才有想法。
考虑枚举一条边作为第 $k$大， 那么如果把所有的边减去这个 $w_k$并对 $0$取 $\max$， 然后如果把权补回来， 那么就求出了一条合法的路径。
考虑直接大力枚举每条边和初始不变的情况计算， 那么 $Ans = \min_{w_k}{Dis_{n} + k \times w_k}$。
下面考虑证明这个事情。
令 $l$表示答案的路径长度。
- 若 $l \geq k$。
- 如果路径上有 $> k$条变化后有权值的边，那么当前答案会 $\geq ans$。因为多出来的边应该不算。
- 如果路径上有 $\leq k$条变化后有权值的边，那么当前答案会 $\geq ans$。因为多加了。
- 当当前枚举的 $w$恰好是答案路径的 $w_k$时， 当前答案就是 $ans$， 所以正确。
- 若 $l < k$
- 当 $w = 0$的时候答案正确。
综上可以发现在没有取到答案的时候我们的做法会使答案变大， 恰好取到的时候会是答案， 直接最短路即可。
0 条评论