#P4152. [AMPPZ2014]The Captain

    ID: 3368 传统题 2000ms 256MiB 尝试: 3182 已通过: 744 难度: 5 上传者: 标签>CF1800普及+/提高-排序链优化建图Dijkstra二叉堆懒删除鸣谢Claris上传

[AMPPZ2014]The Captain

题目描述

给定平面上的 nn 个点,定义 (x1,y1)(x_1,y_1) 到 (x2,y2)(x_2,y_2) 的费用为 min⁡(∣x1−x2∣,∣y1−y2∣)\min(|x_1-x_2|,|y_1-y_2|),求从 11 号点走到 nn 号点的最小费用。

输入格式

第一行包含一个正整数 nn,表示点数。

接下来 nn 行,每行包含两个整数 xi,yix_i,y_i,依次表示每个点的坐标。

输出格式

一个整数,即最小费用。

5
2 2
1 1
4 5
7 1
6 7
2

数据规模与约定

对于 100%100\% 的数据,2≤n≤2×1052\leq n\leq 2\times 10^5,0≤xi,yi≤1090\leq x_i,y_i\leq 10^9。