【BZOJ】4152: [AMPPZ2014]The Captain【SLF优化Spfa】

4152: [AMPPZ2014]The Captain

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 2107  Solved: 820
[Submit][Status][Discuss]

Description

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

Input

第一行包含一个正整数n(2<=n<=200000)，表示点数。

接下来n行，每行包含两个整数x[i],y[i](0<=x[i],y[i]<=10^9)，依次表示每个点的坐标。

 

 

Output

一个整数，即最小费用。

Sample Input

5
2 2
1 1
4 5
7 1
6 7

Sample Output

2

HINT

 

Source

鸣谢Claris上传

---

Solution

这道题本身很简单，分别按$x$、$y$排序相邻间建边跑最短路就可以了，可是这道题卡$Spfa$，可以用$Dijistra$，这里学习了一种玄学（？）优化

SLF优化$Spfa$，如果当前加入的点$dis$比队首小就放到队首，其它照常放在队尾，最优可以卡到$O(nlog_n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000;

struct ED {
    int v, nex, w;
} Edge[800008];

int h[200006], stot;
void add(int u, int v, int w) {
    Edge[++stot].v = v, Edge[stot].nex = h[u], Edge[stot].w = w;
    h[u] = stot;
}

int n;
struct Node {
    int x, y, id;
} a[200005];
bool cmp1(Node a, Node b) { if(a.x == b.x) return a.y < b.y; return a.x < b.x;}
bool cmp2(Node a, Node b) { if(a.y == b.y) return a.x < b.x; return a.y < b.y;}

LL dis[200005];
int vis[200005], q[200005];
void spfa() {
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    vis[1] = 1;    dis[1] = 0;
    int s = 1, t = 0, tot = 1;
    q[++t] = 1;
    while(tot) {
        int x = q[s]; tot --; s = (s + 1) % N;
        vis[x] = 0;
        for(int i = h[x]; i; i = Edge[i].nex) {
            int v = Edge[i].v;
            if(dis[v] > dis[x] + Edge[i].w) {
                dis[v] = dis[x] + Edge[i].w;
                if(!vis[v]) {
                    vis[v] = 1; tot ++;
                    if(dis[v] <= dis[q[s]]) {
                        s = (s - 1 + N) % N;
                        q[s] = v;
                    } else {
                        t = (t + 1) % N;
                        q[t] = v;
                    }
                }
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)    scanf("%d%d", &a[i].x, &a[i].y), a[i].id = i;
    sort(a + 1, a + 1 + n, cmp1);
    for(int i = 1; i < n; i ++) {
        int a1 = a[i].x, a2 = a[i + 1].x, b1 = a[i].y, b2 = a[i + 1].y;
        add(a[i].id, a[i + 1].id, a2 - a1);    add(a[i + 1].id, a[i].id, a2 - a1);
    }
    sort(a + 1, a + 1 + n, cmp2);
    for(int i = 1; i < n; i ++) {
        int a1 = a[i].x, a2 = a[i + 1].x, b1 = a[i].y, b2 = a[i + 1].y;
        add(a[i].id, a[i + 1].id, b2 - b1);    add(a[i + 1].id, a[i].id, b2 - b1);
    }
    spfa();
    printf("%lld", dis[n]);
    return 0;
}