题解 CF1422D 【Returning Home】

· · 题解

首先拿到这道题，切比雪夫距离？然后最短路，然后这给的 1e5 个点还让我求最短路，再一算，貌似这个 m ^ 2 建图要爆，然后自然而然就想到了优化建图。

首先我们可以先想个问题：这道题是否有无用边？很明显对于一道蓝题而言优化建图的东西不可能来一个线段树优化建图之类的难码东西(更何况这是个 D )，所以我们完全可以从无用边的角度来优化建图。

观察到如果我们从 x1 走到 x2 ，如果中间有传送点 x3 的话我完全可以先走到 x3 然后再走到 x2 去，至少这是不劣的。

于是我们根据 x 坐标排序然后两两连边，接着根据 y 坐标排序然后两两连边，最后跑一个 Dij 即可。 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Len = 5e5 + 5;
const long long Inf = 1e18; 
bool f[Len];
int n,m,s,t,cnt,head[Len];
long long dis[Len];
bool flag[Len];
struct node
{
    int next,to;
    long long w;    
}edge[Len << 1];
struct Node
{
    int x;
    long long Dis;
    bool operator < (const Node &Ano) const
    {
        return Dis > Ano.Dis;
    }
}P,C;
void add(int from,int to,long long w)
{
    edge[++ cnt].to = to;
    edge[cnt].next = head[from];
    edge[cnt].w = w;
    head[from] = cnt;
}
void Dij()
{
    priority_queue<Node> q;
    for(int i = 1 ; i <= m ; i ++) dis[i] = Inf , f[i] = false;
    dis[t] = Inf , f[t] = false;
    dis[s] = 0 , f[s] = false;
    P.x = s , P.Dis = 0;
    q.push(P);
    while(!q.empty())
    {
        P = q.top() ; q.pop();
        if(P.x == t) 
        {
            printf("%lld\n",P.Dis);
            return;
        }
        if(!f[P.x])
        {
            f[P.x] |= 1;
            for(int e = head[P.x] ; e ; e = edge[e].next)
            {
                int to = edge[e].to;
                if(dis[to] > dis[P.x] + edge[e].w)
                {
                    dis[to] = dis[P.x] + edge[e].w;
                    if(!f[to])
                    {
                        C.x = to , C.Dis = dis[to];
                        q.push(C);
                    }
                }
            }
        }
    }
    printf("%lld\n",dis[t]);
} 
struct Point
{
    int x,y,id;
}PPt[Len],S,T;
bool cmt(Point x,Point y){return x.x < y.x;}
bool cmq(Point x,Point y){return x.y < y.y;}
long long ddis(Point x,Point y){return min(abs(x.x - y.x) , abs(x.y - y.y));}
long long DDis(Point x,Point y){return abs(x.x - y.x) + abs(x.y - y.y);}
signed main()
{
    scanf("%lld %lld",&n,&m);
    s = m + 1 , t = m + 2;
    scanf("%lld %lld %lld %lld",&S.x,&S.y,&T.x,&T.y);
    S.id = m + 1 , T.id = m + 2;
    for(int i = 1 ; i <= m ; i ++) 
    {
        scanf("%lld %lld",&PPt[i].x,&PPt[i].y);
        PPt[i].id = i;
        add(PPt[i].id , S.id , ddis(PPt[i] , S));
        add(S.id , PPt[i].id , ddis(PPt[i] , S));
        add(PPt[i].id , T.id , DDis(PPt[i] , T));
        add(T.id , PPt[i].id , DDis(PPt[i] , T));
    }
    add(S.id , T.id , DDis(S , T));
    sort(PPt + 1 , PPt + 1 + m , cmt);
    for(int i = 1 ; i <= m ; i ++)
    {
        if(i != 1)
        {
            add(PPt[i].id , PPt[i - 1].id , ddis(PPt[i] , PPt[i - 1]));
            add(PPt[i - 1].id , PPt[i].id , ddis(PPt[i] , PPt[i - 1]));
        }
    }
    sort(PPt + 1 , PPt + 1 + m , cmq);
    for(int i = 1 ; i <= m ; i ++)
    {
        if(i != 1)
        {
            add(PPt[i].id , PPt[i - 1].id , ddis(PPt[i] , PPt[i - 1]));
            add(PPt[i - 1].id , PPt[i].id , ddis(PPt[i] , PPt[i - 1]));
        }
    }
    Dij();
    return 0;
}