the Captain题解；

很显然这个题是让找最短路；

这种通过一个节点到达另一个点的路径我们可以想到dijkstra，然后这道题我们可以看到点是比较多的，所以我们怎么存图呢？

首先我们对于任意三个点，A（x1,y2）,B(x2,y2)，C（x3,y3）（假设A，B,，C相邻），我们画个图，如果我们直接从A到C那么我们走的将会是x的累和取min y的累和，但如果从a到b再到c我们取得是x的差值，y的差值取min加上b到c的距离，通过计算比较，是比直接到省时间的，推广到四个点也是，但是要保证相邻两个点建图，所以我们进行对x从小到大排序，相邻建图，并把边权赋为x的差值，然后进行y的操作同上，那么两点之间有两条边，两个权值，我们将寻找比较并最小权值的任务交给dijkstra啦；这里我用到了堆优化；还有心酸的调试过程...

事实证明，这个题卡spfa..所以堆优化的时间复杂度确定；

#include<algorithm>

#include<bitset>

#include<cctype>

#include<cerrno>

#include<clocale>

#include<cmath>

#include<complex>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<deque>

#include<exception>

#include<fstream>

#include<functional>

#include<limits>

#include<list>

#include<map>

#include<iomanip>

#include<ios>

#include<iosfwd>

#include<iostream>

#include<istream>

#include<ostream>

#include<queue>

#include<set>

#include<sstream>

#include<stack>

#include<stdexcept>

#include<streambuf>

#include<string>

#include<utility>

#include<vector>

#include<cwchar>

#include<cwctype>

#define inf 0x3f

using namespace std;

#define pii pair<int,int>

inline int read()

{

    int x=,f=;

    char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

    while(isdigit(ch)) {x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*f;

}

struct pink

{

    int x,y,id;

}h[];

struct gg

{

    int y,next,v;

}a[<<];

bool mycmp1(pink a,pink b)

{

    return a.x<b.x;

}

bool mycmp2(pink s,pink m)

{

    return s.y<m.y;

}

int lin[],n,m,tot;

bool vis[];

long long dis[];

inline void init(int x,int y,int z)

{

    a[++tot].y=y;

    a[tot].v=z;

    a[tot].next=lin[x];

    lin[x]=tot;

}

/*void dijkstra(int s)

{

    priority_queue<pii,vector<pii>,greater<pii> >q;

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

        dis[i]=inf*(i!=s);

    q.push(pii(dis[s],s));

    while(!q.empty())

    {

        pii now=q.top();q.pop();

        int u=now.second;

//        cout<<")"<<u<<endl;system("pause");

        if(dis[u]<now.first)    continue;

        for(int i=lin[u];i;i=a[i].next)

        {

            int v=a[i].y;

            if(dis[v]>dis[u]+a[i].v)

            {

                dis[v]=dis[u]+a[i].v;

                q.push(pii(dis[v],v));

            }

        }

    }

}*/

inline void dijkstra_heap(int s)

{

    memset(dis,0x3f,sizeof(dis));

    memset(vis,,sizeof(vis));

    priority_queue<pii,vector<pii>,greater<pii> >q;

    dis[s]=;

    q.push(make_pair(,s));

    while (!q.empty())

    {

        int x=q.top().second;

        q.pop();

        if (vis[x]) continue;

        vis[x]=;

        for (int i=lin[x];i;i=a[i].next)

        {

            int y=a[i].y;

            if (dis[y]>dis[x]+a[i].v)

            {

                dis[y]=dis[x]+a[i].v;

                q.push(make_pair(dis[y],y));

            }

        }

    }

}

int main()

{

    n=read();

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

        h[i].id=i,h[i].x=read(),h[i].y=read();

    sort(h+,h+n+,mycmp1);

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

        init(h[i].id,h[i+].id,abs(h[i].x-h[i+].x)),init(h[i+].id,h[i].id,abs(h[i].x-h[i+].x));

    sort(h+,h+n+,mycmp2);

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

        init(h[i].id,h[i+].id,abs(h[i].y-h[i+].y)),init(h[i+].id,h[i].id,abs(h[i].y-h[i+].y));

    dijkstra_heap();

    cout<<dis[n]<<endl;

    return ;

}

巴特西

the Captain题解；

最新文章

热门文章