拓扑排序+spfa挂掉了,求调
查看原帖
拓扑排序+spfa挂掉了,求调
1039274
Cypher_404楼主2024/6/10 17:52
#include<bits/stdc++.h>
using namespace std;
#define N 200050
int tot,head[N],n,m,in[N],s,t,vis[N],dis[N];
struct edge
{
    int v,net;
}e[N];
void addedge(int u,int v)
{
    tot++;
    e[tot].v=v;
    e[tot].net=head[u];
    head[u]=tot;
}
queue<int>que;
int main()
{
    memset(dis,0x3f,sizeof dis);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(y==x)
        {
            continue;
        }
        addedge(y,x);
        in[x]++;
    }
    scanf("%d%d",&s,&t);
    que.push(t);
    vis[t]=1;
    vis[s]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        for(int i=head[u];i;i=e[i].net)
        {
            in[e[i].v]--;
            if(in[e[i].v]==0)
            {
                vis[e[i].v]=1;
                que.push(e[i].v);
            }
        }
    }
    que.push(t);
    dis[t]=0;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        for(int i=head[u];i;i=e[i].net)
        {
            if(!vis[e[i].v])
            {
                continue;
            }
            if(dis[e[i].v]>dis[u]+1)
            {
                dis[e[i].v]=dis[u]+1;
                que.push(e[i].v);
            }
        }
    }
    if(dis[s]>1000000000)
    {
        cout<<-1;
        return 0;
    }
    cout<<dis[s];
    return 0;
}
2024/6/10 17:52
加载中...