P2934 [USACO09JAN] Safe Travel G——无向图最短路树及其性质
题面很简单，就是求出不走原本最短路最后一条边的情况下1号点到每个点的距离
一个错误的想法是，一边dijkstra搞掉原本最短路顺便记录最后一条边，然后查询每个点的时候就用这个点的邻接边去重新更新它
但是这样是错的，因为有些后边的点的最短路是依赖于这条边的，所以这些点的最短路也要相应发生改变
既然发现了这种依赖关系，就可以考虑用树来表达它
也就是说，从源点到所有点的所有最短路径并起来是一棵树（最短路径唯一的情况下）
这很显然，联通并且依赖的最后一条边只有一条，n-1条边的无向连通图
接下来考虑最短路树和我们要求的路径有什么关系
发现当断开一条边时，会发生改变的就只有这条边以下的点，而想要再到达这个点就必须走一条跨越两个子树的边
那么首先要证明的是，所走的路径中不在原树上的的只有这一条
如果加入了其它的边，并且优于原本只走一条的路径的话，那么最短路树上本来就应该有这一条边，证毕
于是，我们就只需要找所有跨越这两个子树的边，把它们的答案取一个最小即可
这条边确定后，这条路径的长度就为