80pts 求调
查看原帖
80pts 求调
520855
red_fire楼主2024/12/12 20:03
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+100,M=1e5+100;
const long long INF=0x7fffffff;
struct node{int x,y,id;}g[M],h[M];
struct edge{int y,n,z;}e[M<<2];
struct sta{int id,lim;}q[M<<2];
int n,m;
int stx,sty,edx,edy;
int head[N],cnt;
bool vis[M<<2][2];
long long dis[M<<2][2];
int calc(int x,int y){return 2*abs(h[x].x-h[y].x)+2*abs(h[x].y-h[y].y);}

void ad(int x,int y)
{
    e[++cnt].n=head[x];
    e[cnt].y=y;
    e[cnt].z=calc(x,y);
    head[x]=cnt;
}

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;
}

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m+2;++i)
    {
        scanf("%d%d",&g[i].x,&g[i].y);
        h[i].x=g[i].x;
        h[i].y=g[i].y;
        g[i].id=i;
    }
    stx=g[m+1].x;sty=g[m+1].y;
    edx=g[m+2].x;edy=g[m+2].y;
    sort(g+1,g+m+3,cmp1);
    for(int i=2;i<=m+2;++i)
    {
        if(g[i].x==g[i-1].x)
        {
            ad(g[i].id,g[i-1].id);
            ad(g[i-1].id,g[i].id);
        }
    }
    sort(g+1,g+m+3,cmp2);
    for(int i=2;i<=m+2;++i)
    {
        if(g[i].y==g[i-1].y)
        {
            ad(g[i].id,g[i-1].id);
            ad(g[i-1].id,g[i].id);
        }
    }


}

bool check(int x,int y){return h[x].x==h[y].x;}

void work()
{
    int he=1,ta=0,sst=m+1,edn=m+2;
    long long ans=INF*INF;
    for(int i=1;i<=m+2;++i)
        dis[i][0]=dis[i][1]=ans;
    dis[m+1][0]=dis[m+1][1]=0;
    ++ta;
    q[ta].id=m+1;
    q[ta].lim=0;
    ++ta;
    q[ta].id=m+1;
    q[ta].lim=1;

    vis[m+1][0]=vis[m+1][1]=1;
    // x1==x2 --> lim = 1
    while(he<=ta)
    {
        int u=q[he].id,st=q[he].lim;
        ++he;
        vis[u][st]=0;
        for(int i=head[u],v,nst;i;i=e[i].n)
        {
            v=e[i].y;
            nst=check(u,v);
            int val=calc(u,v)+(nst != st);
            if(dis[v][nst]>dis[u][st]+val)
            {
                dis[v][nst]=dis[u][st]+val;
                if(vis[v][nst]==0)
                {
                    ++ta;
                    vis[v][nst]=1;
                    q[ta].id=v;
                    q[ta].lim=nst;
                }
            }
        }
    }
    ans=min(dis[m+2][0],dis[m+2][1]);
    if(ans==INF*INF)
    {
        cout<<-1;
    }
    else cout<<ans;
}

int main()
{
    init();
    work();
    return 0;
}
2024/12/12 20:03
加载中...