P6961

P6961 感觉很神奇的题。 一条路径的代价是前 \(k\) 大的边的权值和，有个假的做法是每个点维护一个堆，表示走到这个点前 \(k\) 大边的权值，读者可以思考一下这个做法为什么是假的。 既然直接最短路不好处理，自己观察性质，可以发现前 \(k\) 条边权值和等价于每条边边权变为 \(\max( ......