这tm才 橙\color{orange}{橙}橙？？？ 解题思路 显然是一道最短路，不过难就难在连边上。 发现点数可以达到 2×1052 \times 10^52×105，自然不可能全部连边，否则空间爆炸，考虑启发式连边。 定义 disX,Ydis_{X,Y}disX,Y ，为 点 XXX，YYY 之间边的权值。 我们发现，定义 3 个点 A(ax,ay)A(a_x,a_y)A(ax ,ay )，B(bx,by)B(b_x,b_y)B(bx ,by )，C(cx,cy)C(c_x,c_y)C(cx ,cy )，当 ax≥bx≥cxa_x \ge b_x \ge c_xax ≥bx ≥cx ，当三者以 x 的差为边权时，disA,C=disA,B+disB,Cdis_{A,C}=dis_{A,B}+dis_{B,C}disA,C =disA,B +disB,C ；同理，当 ay≥by≥cya_y \ge b_y \ge c_yay ≥by ≥cy ，当三者以 y 的差为边权时，disA,C=disA,B+disB,Cdis_{A,C}=dis_{A,B}+dis_{B,C}disA,C =disA,B +disB,C 。 可能这里没有看出什么，但是事实上，意味着我们只需要将自己与自己 x 和 y 分别相邻的 4 个（或者更少）点连边，就可以了。用 sort 排序两遍就可以了。 AC 代码（略显多余） 这怎么说都至少是 绿\color{green}{绿}绿 吧，dijkstra 本身都是 黄\color{yellow}{黄}黄 了。 还是说我大炮轰蚊子了？ 赞美出题人和神奇的评级系统\color{white}{赞美出题人和神奇的评级系统}赞美出题人和神奇的评级系统