Aaronwrq @ 2023-08-14 16:14:44
本题前几篇题解不够详细，建议再看看tzc_wk 的题解。
Q：用分割线上的点更新答案有什么用？
A：对于跨越分割线的询问，其最短路径必定经过分割线，用分割线上的点更新答案后，这些点的答案就已经确定，无需继续进入递归。
对于不跨越分割线的询问，把询问按分割线分开。对于分割线每一侧的询问，有两种情况：第一种为最短路径经过分割线，第二种为最短路不经过分割线。最短路经过分割线的在枚举分割线上点时就已经被解决，递归时只需要处理不经过分割线的情况。由于不经过分割线，对于这些询问，分割线对面的那一半就可以直接扔掉，于是长或宽的规模减半。
Q：此题如何卡常？
A：其实不用卡。开了O2用dij可以稳过，加上题解的最短路上界优化可以轻松把时间最长的点降到700ms以内。不开O2很难。
Q：为什么我WA了？
A：如果你求出的最短路与答案完全不同，请优先检查最短路算法。如果你求出的最短路有些正确，有些大于答案，那么有两种可能的错误：
1.只更新了跨越分割线的答案。不跨越分割线的答案也可能经过分割线再回去。
2.将函数内变量写成全局变量。每次调用时递归函数时全局变量都会被更新，可能导致传参错误。我因为这个问题调了一下午。全局变量不安全，警钟长鸣。
Q：还是不理解/代码出错
A：请仔细看题解或比对题解代码。不要只盯着前几篇题解。
by Aaronwrq @ 2023-08-14 16:28:47
可以在LibreOJ上下载到此题数据。
by Last_Flame @ 2023-08-14 18:12:50
orz @Aaronwrq %%%
by syk666 @ 2023-10-10 17:43:06
说得道理
by tzl_Dedicatus545 @ 2023-12-03 21:30:51
@Aaronwrq 经过分割线再回去不是严格劣得嘛qwq，不是很懂
by Aaronwrq @ 2023-12-03 21:49:36
@tzl_Dedicatus545 不一定，比如跨过分割线的全零路径。
by tzl_Dedicatus545 @ 2023-12-05 14:03:04
@Aaronwrq 啊，边权>=1啊qwq
by Aaronwrq @ 2023-12-05 14:13:46
@tzl_Dedicatus545 差不多的道理
by tzl_Dedicatus545 @ 2023-12-05 14:14:44
@Aaronwrq 懂了qwq
by _NTT_ @ 2024-01-11 10:55:57
@Aaronwrq 大佬太感谢了 /bx 一年前的帖子还能帮我 /ll
by xiezheyuan @ 2024-02-13 21:31:47
@Aaronwrq 感谢lz救命！
添加一个 WA 原因：