这个蒟蒻很是不明白
查看原帖
这个蒟蒻很是不明白
760776
zzy_zzy楼主2023/12/23 11:33
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int x,y,id;
}zb[1000010];
bool cmp1(node x,node y){
    // if(x.x==y.x){
    //     return x.y>y.y;
    // }    //注意看
    return x.x<y.x;
}
bool cmp2(node x,node y){
    // if(x.y==y.y){
    //     return x.x>y.x;
    // }    //注意看
    return x.y<y.y;
}
struct H{
    int Next,to,w;
}e[4000010];
int head[2000010],cnt;
void add(int x,int y,int z){
    e[++cnt]=(H){head[x],y,z};
    head[x]=cnt;
}
int dis[4000010];
bool vis[4000010];
int n,m;
void Dij(int st){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
    for(int i=1;i<=2*m;i++){
        dis[i]=INT_MAX;
        vis[i]=0;
    }
    dis[st]=0;
    q.push(make_pair(0,st));
    while(q.size()){
        int u=q.top().second;
        q.pop();
        if(vis[u]){
            continue;
        }
        vis[u]=1;
        for(int i=head[u];i;i=e[i].Next){
            int y=e[i].to;
            if(dis[u]+e[i].w<dis[y]){
                dis[y]=dis[u]+e[i].w;
                q.push(make_pair(dis[y],y));
            }
        }
    }
}

signed main(){
    cin>>n>>m;
    m+=2;
    for(int i=1;i<=m;i++){
        cin>>zb[i].x>>zb[i].y;
        禁止=抄袭;//这个地方不重要
    }
    sort(zb+1,zb+m+1,cmp1);
    for(int i=2;i<=m;i++){
        if(zb[i].x==zb[i-1].x){
            add(zb[i-1].id,zb[i].id,abs(zb[i-1].y-zb[i].y)*2);
            add(zb[i].id,zb[i-1].id,abs(zb[i-1].y-zb[i].y)*2);
        }
    }
    sort(zb+1,zb+m+1,cmp2);
    for(int i=2;i<=m;i++){
        if(zb[i].y==zb[i-1].y){
            add(zb[i-1].id+m,zb[i].id+m,abs(zb[i-1].x-zb[i].x)*2);
            add(zb[i].id+m,zb[i-1].id+m,abs(zb[i-1].x-zb[i].x)*2);
        }
    }
    for(int i=1;i<=m-2;i++){
        add(i,i+m,1);
        add(i+m,i,1);
    }
    add(m-1,2*m-1,0);
    add(2*m-1,m-1,0);
    add(m,2*m,0);
    add(2*m,m,0);
    Dij(m-1);
    if(dis[m]==INT_MAX){
        dis[m]=-1;
    }
    cout<<dis[m];
    return 0;
}

上述代码把8~10,14~16解注就能A,不解注就全WA,有大佬能讲一讲嘛

2023/12/23 11:33
加载中...