BZOJ4152【AMPPZ2014】The Captain <最短路>

Problem

【AMPPZ2014】The Captain

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

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

Input

第一行包含一个正整数$n$($2\le n\le 2\times 10^5$)，表示点数。
接下来$n$行，每行包含两个整数$x[i]$,$y[i]$($0\le x[i],y[i]\le 10^9$)，依次表示每个点的坐标。

Output

一个整数，即最小费用。

Sample Input

5
2 2
1 1
4 5
7 1
6 7

Sample Output

2

标签：最短路

Solution

一道比较基础的最短路变形。
不难发现，在一个凸壳上，如果走任意一条弦，显然没有直接沿着凸壳走优。
所以分别按$x$和$y$排两次序，相邻点连边，可得到一个图。在此图上跑最短路即可。
注意，此题卡$SPFA$（大佬：不错啊，卡错误算法天经地义~）

Code

#include <bits/stdc++.h>
#define MAX_N 200000
#define fir first
#define sec second
#define mp make_pair
#define pli pair<lnt,int>
using namespace std;
typedef long long lnt;
int n;    lnt dis[MAX_N+5];
vector <int> G[MAX_N+5], E[MAX_N+5];
struct node {int id, x, y;} p[MAX_N+5];
bool cmpx(const node &a, const node &b) {return a.x < b.x;}
bool cmpy(const node &a, const node &b) {return a.y < b.y;}
void addedgex(int u, int v, int a, int b) {G[u].push_back(v), E[u].push_back(p[b].x-p[a].x);}
void addedgey(int u, int v, int a, int b) {G[u].push_back(v), E[u].push_back(p[b].y-p[a].y);}
void Dijkstra() {
    memset(dis, 0x7f, sizeof dis), dis[1] = 0;
    priority_queue <pli> que;	que.push(mp(0LL, 1));
    bool mrk[MAX_N+5];	memset(mrk, false, sizeof mrk);
    while (!que.empty()) {
        int u = que.top().sec;	que.pop();
        if (mrk[u])	continue;	mrk[u] = true;
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i];	lnt c = E[u][i];
            if (mrk[v] || dis[u]+c > dis[v])	continue;
            dis[v] = dis[u]+c, que.push(mp(-dis[v], v));
        }
    }
}
int main() {
    scanf("%d", &n);	for (int i = 1; i <= n; i++) p[i].id = i, scanf("%d%d", &p[i].x, &p[i].y);
    sort(p+1, p+n+1, cmpx);	for (int i = 1; i < n; i++) addedgex(p[i].id, p[i+1].id, i, i+1), addedgex(p[i+1].id, p[i].id, i, i+1);
    sort(p+1, p+n+1, cmpy);	for (int i = 1; i < n; i++)	addedgey(p[i].id, p[i+1].id, i, i+1), addedgey(p[i+1].id, p[i].id, i, i+1);
    Dijkstra();	printf("%lld", dis[n]);	return 0;
}