XIV POI Etap 3 Koleje 题解
好像没人写题解啊。看起来就是要求关键点的最小斯坦呐树，那么考虑经典的，dfs 序会经过树上每条边两次，所以考虑从每个关键点出发跑 dijkstra，得到关键点两两之间的最短路，然后直接用它跑一个 prim。
正确性，注意到对于一个最优解，沿着它的一个 dfs 序走，就会得到若干条关键点之间的路径，它们串起来得到一条经过每个关键点至少一次的路径，而这些路径的长度和不超过最优解的两倍。显然每条路径不短于我们求出的最短路，于是我们用这些最短路求出的 mst 不比沿着这个 dfs 序走得到的链长，于是它不可能超过最优解的两倍。
实现就是两个板子。