Petersburg

题目链接：https://codeforces.com/contest/1912/attachments/download/23419/icpc-nerc-2023-statements.pdf 题意简述 相信大家都听说过经典的接雨水问题。给定 \(n\) 个数作为初始的地砖高度分布 \(a_i\) ......

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