20191015 练习：spfa

83 阅读 0 评论 55 点赞

我是靠谱客的博主彪壮冬日，这篇文章主要介绍20191015 练习：spfa，现在分享给大家，希望可以做个参考。

总览：

bfs版+dfs版

判负权回路加记数数组，经历一个点n+1次时即存在负权回路。

bfs版模板：

struct gg
{
int to,w;
};
int s[N];
bool ex[N];
vector <gg> ljb[N];
queue <int> q;
void spfa_bfs(int begin)
{
s[begin]=0;
q.push(begin);
ex[begin]=1;
while(!q.empty())
{
int x=q.front();
for(int y=0;y<ljb[x].size();y++)
{
gg z=ljb[x][y];
if(s[z.to]>s[x]+z.w)
{
s[z.to]=s[x]+z.w;
if(!ex[z.to])
{
q.push(z.to);
ex[z.to]=1;
}
}
}
}
}

dfs版模板：

struct gg
{
int to,w;
};
int s[N];
vector <gg> ljb[N];
void spfa_dfs(int x)
{
for(int y=0;y<ljb[x].size();y++)
{
gg z=ljb[x][y];
if(s[z.to]>s[x]+z.w)
{
s[z.to]=s[x]+z.w;
spfa_dfs(z.to);
}
}
}