题解 | J 蚂蚁聚会

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