（芭芭拉太可爱了叭......）
题目描述
在企鹅国，企鹅们是通过滑冰出行的。每次滑冰需要选择一个营地作为起点，一个营地作为终点，然后从营地 \(A(a_x,a_y)\) 滑到营地 \(B(b_x,b_y)\) 需要的时间是 \(min \{|a_x-b_x |,|a_y-b_y | \}\)。
现在企鹅豆豆在 \(1\) 号营地，他需要赶到 \(N\) 号营地参加活动，他想知道他最少需要花费多少时间？
可能存在营地重合的情况。
输入格式
第一行一个整数 \(n\) ，代表营地个数。
接下来 \(n\) 行，每行 \(2\) 个数字 \(x_i，y_i\) ，表示一个营地的坐标。
输出格式
输出一个整数表示需要的最少时间。
样例 #1
样例输入 #1
5
2 2
1 1
4 5
7 1
6 7
样例输出 #1
2
提示
【样例说明】
从营地 \(1\) 先到达营地 \(4\) ，花费 \(1\) 单位时间。
再从营地 \(4\) 到达营地 \(5\)，花费 \(1\) 单位时间。
【数据范围】
对于 \(5\%\) 的数据，\(x_i=y_i\)。
对于 \(30\%\) 的数据，\(n≤1000\)。
对于另外 \(35\%\) 的数据，\(x_i,y_i\) 均单调不减。
对于 \(100\%\) 的数据，\(1≤n≤2×10^5,0≤x_i,y_i≤10^9\)。
解析
我们可以用最短路的算法解决这道题，n个点并不需要两两之间都要连边，例如\(x_i<x_j<x_k\)，其中i和j连边，j和k连边，这样i和k就不需要再连了，所以我们可以对横坐标排序连一次边，纵坐标也连一次，在图上跑最短路算法即可。
代码
#include <bits/stdc++.h>
#define P pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 10, inf = 1e9 + 10;
int n, d[N];
vector<P> e[N];
struct node {
int x, y, id;
}a[N];
bool vis[N];
bool cmp1(node a, node b) {return a.x < b.x;}
bool cmp2(node a, node b) {return a.y < b.y;}
void dij() {
priority_queue<P> q;
for (int i = 1; i <= n; i ++) d[i] = inf;
d[1] = 0; q.push({0, 1});
while (!q.empty()) {
int x = q.top().se; q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (int i = 0; i < e[x].size(); i ++) {
int y = e[x][i].fi;
int z = e[x][i].se;
if (d[y] > d[x] + z) {
d[y] = d[x] + z;
q.push({-d[y], y});
}
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i].x >> a[i].y;
a[i].id = i;
}
sort(a + 1, a + n + 1, cmp1);
for (int i = 1; i < n; i ++) {
e[a[i].id].push_back({a[i + 1].id, a[i + 1].x - a[i].x});
e[a[i + 1].id].push_back({a[i].id, a[i + 1].x - a[i].x});
}
sort(a + 1, a + n + 1, cmp2);
for (int i = 1; i < n; i ++) {
e[a[i].id].push_back({a[i + 1].id, a[i + 1].y - a[i].y});
e[a[i + 1].id].push_back({a[i].id, a[i + 1].y - a[i].y});
}
dij();
cout << d[n] << '\n';
return 0;
}
