题意，求1到n的最短路。不难想到单源最短路，难点在于数量级太大，因此如何建图是关键；

因为cost =  min{|Xi-Xj|, |Yi-Yj|}；所以，点i的移动只有两种情况，. x距离最近的点，. y距离最近的点 

如此一来，每个点i的最多只有四条边（为什么是四条?）,这样复杂度就降下来了，单源最短路的复杂度为n*m（点*边数） 

我用spfa。 

解题思路： 

x轴排序，建图 

y轴排序，建图 

求最短路 

用spfa注意队列que的大小至少是n*m，可以使用循环队列 

#include <cstdio>

#include <cstring>

#include <vector>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = ;

struct node

{

    int v;

    int i;

    bool operator < (const node &t)const

    {

        return v < t.v;

    }

}x[N],y[N];

vector<int>g[N];

int p[N][];

int ABS(int x)

{

    return x >=  ? x : -x;

}

long long get_value(int i,int j)

{

    return min(ABS(p[i][]-p[j][]),ABS(p[i][]-p[j][]));

}

bool flag[N];

long long dist[N];

int que[N];

long long spfa(int s,int n)

{

    memset(flag,false,sizeof(flag));

    memset(dist,0x7f,sizeof(dist));

    int head = ,tail = ;

    dist[s] = ;

    flag[s] = true;

    que[tail++] = s;

    while(head != tail)

    {

        int tep = que[head++];

        if(head >= N) head = ;//循环队列

        flag[tep] = false;

        for(int i = ; i < g[tep].size(); i++)

        {

            int v = g[tep][i];

            if(dist[v] > dist[tep] + get_value(v,tep))

            {

                dist[v] = dist[tep] + get_value(v,tep);

                if(!flag[v])

                {

                    que[tail++] = v;

                    if(tail >= N) tail = ;//循环队列

                    flag[v] = true;

                }

            }

        }

    }

    return dist[n-];

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        for(int i = ; i < N; i++) g[i].clear();

        for(int i = ; i < n; i++)

        {

            scanf("%d %d",&p[i][],&p[i][]);

            x[i].v = p[i][]; x[i].i = i;

            y[i].v = p[i][]; y[i].i = i;

        }

        sort(x,x+n);

        sort(y,y+n);

        for(int i = ; i < n; i++)

        {

            int u = x[i-].i;

            int v = x[i].i;

            //这里可以去下重

            g[u].push_back(v);

            g[v].push_back(u);

        }

        for(int i = ; i < n; i++)

        {

            int u = y[i-].i;

            int v = y[i].i;

            //这里可以去下重

            g[u].push_back(v);

            g[v].push_back(u);

        }

        printf("%lld\n",spfa(,n));

    }

    return ;

}