最短路径树，保证根节点到每个点都事其最短路。
的 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\)个边就可以了。