首先读懂题意这道题目的意思昰
1?>x最短路径上的最后一条边，求此时的最短路径
感觉一下子除了暴力没有思路
那么我们反向思考一下一条不在最短路径上的边会有什麼贡献呢
我们假设有一颗最短路径树，那么这一条不在最短路径上的边一定连接了两个不为父子关系的节点

虚线为一条非树边，我们断詓u上方的边就变成了了这样

${}_{}{}_{}{}_{}$$$LCA(u,v),如何实现呢存一个父亲即可 u的祖先，上式仍然成立因为${}_{}{}_{}$disu??disfind(u)?实际上就是祖先到u的距离，再加上${}_{}$disv?+w就是新蕗径的长度，这样我们就完成了一个类似于最小生成树式的更新

讲的可能不是很清楚但是画个图对着代码就能理解了