我是靠谱客的博主 彪壮冬日,这篇文章主要介绍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);
}
}
}

最后

以上就是彪壮冬日最近收集整理的关于20191015 练习:spfa的全部内容,更多相关20191015内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(55)

评论列表共有 0 条评论

立即
投稿
返回
顶部