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