题解 | J 蚂蚁聚会

公共路径上的所有点 $i$ 满足 $d i s (x 1, i) + d i s (i, y 1) = = d i s (x 1, y 1)$ 且 $d i s (x 2, i) + d i s (i, y 2) = = d i s (x 2, y 2)$ 。如果相邻的两点 $i, j$ 在同一条公共路径上，除了满足上述要求外，还需要 $d i s (x 1, i) - d i s (x 1, j) = = d i s (i, j)$ 且 $a b s (d i s (x 2, i) - d i s (y 2, j)) = = d i s (i, j)$ 。因此，处理四次最短路，遍历所有满足第一个条件的点，和所有相邻的满足第二个条件的点连边。最终得到的新图一定是一棵带权树，拓扑排序求最大深度即可。