实质
关于SPFA，它亖了
就是对Bellman-Ford算法的一种优化。事实证明优化地很成功，直接给BF差不多干没了
可以得出，节点i路程变化，当且仅当指向i的节点的路程变化，然后就能写出一个接近bfs的算法。
特性
通常情况下，SPFA是快于Dijkstra的。
！！！但是！SPFA它亖了容易被卡啊！被卡了就真亖了！！！
实现
- 把起点插入队列
- 取出队头，更新队头的所有出边。
- 每个更新成功的出边，都把另一个节点插入队列。
- 重复执行2、3步直到队列为空。
有没有发现长得很像堆优化的Dijkstra？像就对了(^▽^)
注意：不同于Dij，SPFA存储的判断数组是判断元素是否在队列中（可重复访问），而Dij的是判断元素有没有被访问过（不可重复访问）
同时，因为负环的存在，是不存在“剪枝”操作的~
判断负环
顺便记录一下路径经过的点个数，如果个数超过n，就说明有环了。这个环还能被更新，就说明它是个负环。
注意，开始时所有点都是起点。
代码
最短路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1.5e5+5;
int n,m;
int x,y,z;
int dis[N];
int idk;
int hd[N],ne[N],to[N],ed[N];
void merge(int u,int v,int x){
ed[++idk]=x;
to[idk]=v;
ne[idk]=hd[u];
hd[u]=idk;
}
void spfa(int be,int en){
memset(dis,0x3f,sizeof(dis));
bool inq[N]={false};
queue<int> q;
q.push(be);
dis[be]=0;
inq[be]=true;
while(!q.empty()){
int now=q.front();q.pop();
inq[now]=false;
for(int i=hd[now];i;i=ne[i]){
if(dis[to[i]]>dis[now]+ed[i]){
dis[to[i]]=dis[now]+ed[i];
if(!inq[to[i]]){
q.push(to[i]);
inq[to[i]]=true;
}
}
}
}
if(dis[en]==0x3f3f3f3f)cout<<"impossible";
else cout<<dis[en];
}
int main(){
cin>>n>>m;
while(m--){
cin>>x>>y>>z;
merge(x,y,z);
}
spfa(1,n);
return 0;
}
|
判断负环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1.5e5+5;
int n,m;
int x,y,z;
int dis[N],cnt[N];
int idk;
int hd[N],ne[N],to[N],ed[N];
void merge(int u,int v,int x){
ed[++idk]=x;
to[idk]=v;
ne[idk]=hd[u];
hd[u]=idk;
}
bool spfa(){
bool inq[N]={false};
queue<int> q;
for(int i=1;i<=n;i++){
q.push(i);
cnt[i]=1;
inq[i]=true;
}
while(!q.empty()){
int now=q.front();q.pop();
inq[now]=false;
for(int i=hd[now];i;i=ne[i]){
if(dis[to[i]]>dis[now]+ed[i]){
dis[to[i]]=dis[now]+ed[i];
cnt[to[i]]=cnt[now]+1;
if(cnt[now]>n)return true;
if(!inq[to[i]]){
q.push(to[i]);
inq[to[i]]=true;
}
}
}
}
return false;
}
int main(){
cin>>n>>m;
while(m--){
cin>>x>>y>>z;
merge(x,y,z);
}
if(spfa())cout<<"Yes";
else cout<<"No";
return 0;
}
|
完结撒花o(￣︶￣)o