DGL__DGL_AFO @ 2024-05-13 20:59:14
这为啥RE啊
记录
#include<bits/stdc++.h>
using namespace std;
int h[114514],e[214514],ne[214514],w[214514],idx;
int n,m,s;
int a,b,c;
int d[114514];
bool st[114514];
int q[114514],t=1,ww;
void add(int a,int b,int c)
{
idx++;
ne[idx]=h[a];
e[idx]=b;
w[idx]=c;
h[a]=idx;
}
void spfa()
{
q[++ww]=1;
while(ww>=t)
{
int x=q[t];t++;
st[x]=0;
for(int i=h[x];i;i=ne[i])
{
int y=e[i],z=w[i];
if(d[y]>d[x]+z)
{
d[y]=d[x]+z;
if(!st[y])
{
q[++ww]=y;
st[y]=1;
}
}
}
}
}
int main()
{
//memset(h,-1,sizeof h);
cin>>n>>m>>s;
memset(d,0x3f,sizeof d);
d[s]=0;st[s]=true;
while(m--)
{
cin>>a>>b>>c;
add(a,b,c);
}
spfa();
for(int i=1;i<=n;i++)
cout<<d[i]<<' ';
return 0;
}
by Super_Cube @ 2024-05-13 21:04:11
@DGL__DGL q 开小了吧。每个元素不止入队一次。
by Special_Tony @ 2024-05-13 21:04:30
@DGL__DGL 题目背景告诉你SPFA死了。
by DGL__DGL_AFO @ 2024-05-13 21:06:14
@Super_Cube
q开到 11451444 都不行()
by Super_Cube @ 2024-05-13 21:06:27
@DGL__DGL 对啊,你打 spfa 该去交弱化版那道啊。
by DGL__DGL_AFO @ 2024-05-13 21:06:43
@Special_Tony
它不能死 RE 上吧
by DGL__DGL_AFO @ 2024-05-13 21:07:34
想看看卡SPFA的特构数据长啥样
by Special_Tony @ 2024-05-13 21:10:26
@DGL__DGL 菊花图SPFA重复进队次数过多导致队列溢出?
by Super_Cube @ 2024-05-13 21:11:41
@Special_Tony @DGL__DGL 就是这样。一个点可以入很多次。
by Special_Tony @ 2024-05-13 21:11:52
@DGL__DGL 卡spfa用菊花图,边类似这样:
1 2
1 3
1 4
1 5
1 6
...
1 n
by Special_Tony @ 2024-05-13 21:12:35
@DGL__DGL 所以我劝你写dijk,SPFA不可能AC这题