【例题讲解】The Captain：最短路无效边去重

本文主要是介绍【例题讲解】The Captain：最短路无效边去重，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。

Solution

这道题如果暴力建边，那么对于$n\le 200000$的复杂度$n^2$条边显然是不行的。

因此这道题的主要思路就是去除无效的边，最后进行最短路。

我们思考一下，对于三个点$a,b$和$c$，若$xa\le xb\le xc$，则：

当$a$和$c$的具体取$△x1$，$a$和$b$取$△x2$，$b$和$c$取 △ x 3 △x3

这篇关于【例题讲解】The Captain：最短路无效边去重的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---