模板 - SPFA
2024-08-30 03:54:02
SPFA可以用来判断负环或者计算带负权的最短路。
其实带负权的最短路可以用带势Dijkstra计算……
所以SPFA基本就拿来判负环了……
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace SPFA{
const int MAXN=5010;
const int MAXM=10010;
const int INF=0x3f3f3f3f;
int tol;
int head[MAXN];
struct Edge{
int to,next,cost;
}edge[MAXM];
void init(){
tol=1;
memset(head,-1,sizeof(head));
}
void add_edge(int u,int v,int cost){
edge[tol].to=v;
edge[tol].cost=cost;
edge[tol].next=head[u];
head[u]=tol++;
}
bool vis[MAXN];
int cnt[MAXN];
int dist[MAXN];
bool spfa(int s,int n){
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
memset(dist,0x3f,sizeof(dist));
queue<int>que;
while(!que.empty())que.pop();
que.push(s);
vis[s]=true;
cnt[s]=1;
dist[s]=0;
while(!que.empty()){
int u=que.front();
que.pop();
vis[u]=false;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(dist[v]>dist[u]+edge[i].cost){
dist[v]=dist[u]+edge[i].cost;
if(!vis[v]){
vis[v]=true;
que.push(v);
if(++cnt[v]>n){
return false;
}
}
}
}
}
return true;
}
}
using namespace SPFA;
最新文章
- Sql Server系列:视图
- JavaScript Patterns 6.4 Prototypal Inheritance
- MWeb
- zk框架中利用map类型传值来创建window,并且传值
- Jenkins问题汇总
- css3 盒模型记
- effective c++ 条款11 Handle assignment to self in operator=
- 百度官方wormHole后门检测记录(转)
- Code Forces 414B 很不错的双手,以促进合规
- iOS 调试 之 打印
- Linux文件锁定保护命令chattr介绍
- 第一册:lesson 119.
- 【NLP】Conditional Language Modeling with Attention
- python使用adb获取Android Phone截图(解决Windows传输编码导致png文件损坏的问题)
- 怎么在Mac中的Safari查看网页源码
- 比较C#中几种常见的复制字节数组方法的效率
- [Spark][Python][Application]非交互式运行Spark Application 的例子
- 2018牛客网暑假ACM多校训练赛(第七场)I Tree Subset Diameter 动态规划 长链剖分 线段树
- Python一行代码处理地理围栏
- (网页)js常见报错之Unexpected token in JSON at position
热门文章
- 性能测试--Jmeter随机生成/随机选取/csv读取关键字
- 远程服务器上的weblogic项目管理(一)项目部署与更新流程
- CSS各种度量单位----px、em、%、rem、vh/vw、vmin/vmax
- sqlldr 用法
- get_linux_ip_info.sh 获取ip地址
- linux日常开发使用命令整理
- PAT 天梯赛 L2-028. 秀恩爱分得快 【数据处理】
- Android4.4 GPS框架分析【转】
- ubuntn下 apt的用法和yum的比较(转)
- Synchronized之二:synchronized的实现原理