题目链接
题解SPFA 一般时间复杂度为 O ( m ) O(m) O(m),最坏情况下为 O ( n m ) O(nm) O(nm),本质是对 Bellman_ford 算法的优化。可以用于计算正、负边权的最短路,但不能取代 Bellman_ford 计算有步数限制的最短路。单源最短路问题。
思想:
在Bellman_ford算法中需要遍历全部的边来更新最短路,但是 d[b] = min (d[b], d[a] + w)
只有在 d[a]
被更新(变小),d[b]
才有可能变小,所以我们试图将变小的d[b]
对应的b
记录下来,只用这些点去更新最短路。在用这些点更新的过程中再有被更新点就再记录下来。
#include
using namespace std;
const int N = 1e4+10, M = 5e5+10, INF = 0x3f3f3f3f;
int d[N];
bool st[N];
int w[M], e[M], ne[M], h[N], idx;
int n, m, s;
void add (int a, int b, int c) {
w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void spfa () {
memset (d, 0x3f, sizeof d); // !!!
d[s] = 0;
queue q;
q.push (s);
st[s] = true; // 表示 s 是否在队列中,在队列中就不要重复插入了
while (!q.empty ()) {
int t = q.front ();
q.pop ();
st[t] = false;
for (int i = h[t];~i;i = ne[i]) {
int j = e[i];
if (d[j] > d[t] + w[i]) {
d[j] = d[t] + w[i];
if (!st[j])
q.push (j),
st[j] = true; // !!
}
}
}
}
int main() {
memset (h, -1, sizeof h); // !!!
cin >> n >> m >> s;
for (int i = 1;i > a >> b >> c;
add (a, b, c);
}
spfa ();
for (int i = 1;i m;
for (int i = 0;i > a >> b >> c;
add (a, b, c);
}
if (spfa ()) puts ("Yes");
else puts ("No");
return 0;
}
SPFA 判断是否存在以某一点为起点的负环
题目
题目链接
代码#include
using namespace std;
const int N = 2e3+10, M = 1e6+10; // 题目中m的数据范围并非边的上限 !!!因为存在回边
int n, m;
int idx, e[M], ne[M], w[M], h[N];
bool st[N];
int d[N], cnt[N];
void add (int a, int b, int c) {
w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa () {
// 注意很多初始化
memset (cnt, 0, sizeof cnt);
memset (d, 0x3f, sizeof d);
memset (st, false, sizeof st);
d[1] = 0; // 本题起点确定,所以需要初始化
queue q;
q.push (1);
st[1] = false;
while (!q.empty ()) {
int t = q.front ();
q.pop ();
st[t] = false;
for (int i = h[t]; ~i;i = ne[i]) {
int j = e[i];
if (d[j] > d[t] + w[i]) {
d[j] = d[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) {
q.push (j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
int T;
cin >> T;
while (T--) {
memset (h, -1, sizeof h); // 注意初始化
idx = 0; // 注意初始化
cin >> n >> m;
while (m --) {
int a, b, c;
cin >> a >> b >> c;
add (a, b, c);
if (c >= 0) add (b, a, c);
}
if (spfa ()) cout
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?