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 DGL__DGL_AFO @ 2024-05-13 21:12:51
好吧,开到1e9就不RE了
by Super_Cube @ 2024-05-13 21:12:54
@DGL__DGL 改成 stl 的 queue 试了一下,link,就是入队过多导致 tle,你原本的代码就是手写队列开不下。
by DGL__DGL_AFO @ 2024-05-13 21:13:25
感谢诸位,均已关
by Special_Tony @ 2024-05-13 21:15:07
@DGL__DGL 菊花图+SPFA:1->2~n,2->1,1->3~n,3->1……达到O(nm)(a->b表示a节点跟新b节点)
by Super_Cube @ 2024-05-13 21:18:42
@DGL__DGL link,菊花或者网格图,再可以接点诱导链。
by ___A__ @ 2024-05-13 21:31:46
@DGL__DGL 堆优化spfa能过
by Phartial @ 2024-05-13 21:33:18
@_A 堆优化 spfa 是啥,dijkstra 的别称吗/yiw
by 解方橙 @ 2024-05-13 21:34:27
神秘优化spfa也能过,不过一切spfa优化的本质就是把spfa的队列改得更像优先队列
by ___A__ @ 2024-05-13 21:34:57
@bykem 就把spfa队列改成堆 按dis小来排序 复杂度依旧错的
by Special_Tony @ 2024-05-13 21:35:58
@_A 不管怎么说都可以卡(