题目描述
给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。
Solution
这道题如果暴力建边，那么对于 n ≤ 200000 n≤200000 n≤200000的复杂度 n 2 n^2 n2条边显然是不行的。
因此这道题的主要思路就是去除无效的边，最后进行最短路。
我们思考一下，对于三个点 a , b a,b a,b和 c c c，若 x a ≤ x b ≤ x c xa≤xb≤xc xa≤xb≤xc，则：
当 a a a和 c c c的具体取 △ x 1 △x1 △x1， a a a和 b b b取 △ x 2 △x2 △x2， b b b和 c c c取 △ x 3 △x3