这个 spfa 为啥能过(
查看原帖
这个 spfa 为啥能过(
554145
Night_sea_64楼主2024/3/22 21:53

我发了个类似 spfa 的题解,然后上题解区一看,别人跟我做法都不一样

所以这个 spfa 能被卡掉吗

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,s,ans;
struct edge{int x,o,c,l,r,next;}e[1000010];
int head[500010],tail[500010],cur;
void addedge(int x,int y,int o,int c,int l,int r)
{
    e[++cur]=(edge){y,o,c,l,r,0};
    if(!head[x])head[x]=cur;
    else e[tail[x]].next=cur;
    tail[x]=cur;
}
struct node{int x,l;};
int minr[500010][21];
bool flag[500010][21];
void spfa()
{
    memset(minr,999999,sizeof(minr));
    queue<node>q;
    for(int i=1;i<=20;i++)
    {
        minr[s][i]=i;
        q.push({s,i});
    }
    while(!q.empty())
    {
        int x=q.front().x,l=q.front().l,r=minr[x][l];
        q.pop();
        //cout<<x<<" "<<l<<" "<<r<<endl;
        flag[x][l]=0;
        for(int i=head[x];i;i=e[i].next)
        {
            edge y=e[i];
            if(l>=y.o&&r<=y.c)
                if(y.r<minr[y.x][y.l]&&!flag[y.x][y.l])
                {
                    minr[y.x][y.l]=y.r,flag[y.x][y.l]=1;
                    q.push({y.x,y.l});
                }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        int x,y,o,c,l,r;
        scanf("%d%d%d%d%d%d",&x,&y,&o,&c,&l,&r);
        addedge(x,y,o,c,l,r);
    }
    spfa();
    for(int i=1;i<=n;i++)
        if(i!=s)
        {
            int minn=1e9;
            for(int j=1;j<=20;j++)
                minn=min(minn,minr[i][j]);
            if(minn<1e9)ans=max(ans,minn);
        }
    printf("%d\n",ans);
    return 0;
}
2024/3/22 21:53
加载中...