dij堆优化 数组加大之后A了 请问这是为什么呢?
查看原帖
dij堆优化 数组加大之后A了 请问这是为什么呢?
295769
LiuXinru楼主2020/11/8 20:58
#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
typedef double D;
#define pb(i) push_back(i)
#define inf 1000000000
inline LL read()
{
    LL x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void write(LL x)
{
    if (x < 0)
        x = ~x + 1, putchar('-');
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

const int N=1e6+10;
const int M=5e6+10;

int n,m,s,t;

int head[N],tot,fa[N],ca[N],x[N],y[N],dis[N];

bool vis[N];

struct node
{
    int t,next;
} edge[M*2];

struct Rec
{
    int id,dis;
    bool operator < (const Rec &tmp)const
    {
        return dis>tmp.dis;
    }
};

priority_queue<Rec> Q;

void Init()
{
    tot=0;
    memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(fa,0,sizeof(fa));
    memset(ca,0,sizeof(ca));
}

void add(int f,int t)
{
    tot++;
    edge[tot].t=t;
    edge[tot].next=head[f];
    head[f]=tot;
}

void pre()
{
    for(int i=1;i<=n;i++)
    {
        bool flag=true;
        if(fa[i]==1)
        {
            for(int j=head[i];j;j=edge[j].next)
            {
                int tt=edge[j].t;
                if(fa[tt]!=1)
                {
                    flag=false;
                    break;
                }
            }

            if(!flag)
                ca[i]=0;
            else
                ca[i]=1;
        }
    }
}

int bfs()
{
    queue<int> q;
    q.push(t);
    fa[t]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].t;
            if(!fa[v])
            {
                fa[v]=1;
                q.push(v);
            }
        }
    }
}

void dist()
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    Rec rec;
    rec.id=s;
    rec.dis=0;
    dis[s]=0;
    Q.push(rec);
    while(!Q.empty())
    {
        int u=Q.top().id;
        Q.pop();
        if(vis[u])
            continue;
        vis[u]=true;

        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].t;
            if(dis[v]>dis[u]+1&&ca[v])
            {
                dis[v]=dis[u]+1;
                Rec rec;
                rec.id=v;
                rec.dis=dis[v];
                Q.push(rec);
            }

        }
    }
}

int main()
{
    n=read();
    m=read();
    Init();
    for(int i=1; i<=m; i++)
    {
        x[i]=read();
        y[i]=read();
        add(y[i],x[i]);
    }
    s=read();
    t=read();

    bfs();

    tot=0;
    memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));

    for(int i=1;i<=m;i++)
    {
        add(x[i],y[i]);
    }

    pre();
    if(ca[s]==0)
    {
        printf("-1");
        printf("\n");
        return 0;
    }
    dist();

    if(dis[t]!=inf)
    {
        write(dis[t]);
        printf("\n");
    }
    else
        printf("-1\n");
    return 0;
}

之前N 和 M 的定义分别为题目给出的1e4和2e5,2号点WA,把N和M改成这样之后就A了,请问这是为什么呢,拜谢

2020/11/8 20:58
加载中...