【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 = ;

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

int h[], 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[];
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[];
int vis[], q[];
void spfa() {
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    vis[] = ;    dis[] = ;
    int s = , t = , tot = ;
    q[++t] = ;
    while(tot) {
        int x = q[s]; tot --; s = (s + ) % N;
        vis[x] = ;
        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] = ; tot ++;
                    if(dis[v] <= dis[q[s]]) {
                        s = (s -  + N) % N;
                        q[s] = v;
                    } else {
                        t = (t + ) % N;
                        q[t] = v;
                    }
                }
            }
        }
    }
}

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