注意边权相同,最短路即经过边,删边最少,即把两个最短路合并起来
然后发现重合部分可以减少其中距离,考虑s1,s2双源最短路,然后找公共部分来合并起来,假设这个点是 xxx,那就是 1→x+x→s1+x→s21\to x+x\to s_1+x\to s_21→x+x→s1+x→s2。
求正确与否