```cpp
void init(int a,int b,int p)
{
tot++;
next[tot]=head[a];
adj[tot]=b;
weight[tot]=p;
head[a]=tot;
return;
}
void spfa(int s)
{
queue<int> q;
inq[s]=true;
dist[s]=0;
q.push(s);
int top,i;
while(!q.empty())
{
top=q.front();
c[top]=true;
q.pop();
inq[top]=false;
for(i=head[top];i!=0;i=next[i])
{
if(dist[adj[i]]>dist[top]+weight[i])
{
dist[adj[i]]=dist[top]+weight[i];
if(!inq[adj[i]])
{
q.push(adj[i]);
inq[adj[i]]=true;
}
}
}
}
return;
}
没有加inqtimes负权环的判定
```
by shanyuqiang @ 2015-10-12 23:31:16
忽略c[top]=true;= =
by shanyuqiang @ 2015-10-12 23:42:31
谢谢,有用栈优化的吗?
by rpcc_Alex @ 2015-10-13 21:16:42
蒟蒻表示不会qwq
by shanyuqiang @ 2015-10-13 21:56:20
栈。。。 表示我只见过用队列优化的= =
by QWsin @ 2015-10-24 20:23:11
@[url=/space/show?uid=11280]QWsin[/url] SPFA不就是福特算法的队列实现(优化)
by a526955194 @ 2016-01-13 18:10:29
spfa前来考古
by ChthollyTree @ 2018-08-17 12:34:38