我发了个类似 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;
}