最短路径树，保证根节点到每个点都事其最短路。
的 spt 事
怎么求？
我谔谔
只需要在dij/spfa上动一点手脚。
当 \(dis_v>dis_u+edge(u,v)\) 时，把 \(v\) 的前驱标记为 \(u\) 或 \(edge(u,v)\)。
完结撒花!
有时我们需要使SPT边权和最小。
只需要加一个等于， \(dis_v\ge dis_u+edge(u,v)\)。为什么？我们要使满足 SPT 的同时 \(edge(u,v)\) 更小。
明显堆先取出来的 \(dis_u\) 更小。这时 \(dis_v\) 一定（即取等），所以 \(edge(u,v)\) 越大。后取出来的 \(edge(u,v)\) 就越小。
这道题，从根开始遍历，随便怎么取\(k\)个边就可以了。
最短路径树（SPT）/CF1076D Edge Deletion
原文：https://www.cnblogs.com/kkksc0100/p/cf1076d.html