优先队列优化
题目链接
时间复杂度 O ( m l o g n ) O(mlogn) O(mlogn),适合稀疏图,即边少点多。
#include
#define PII pair
#define x first
#define y second
using namespace std;
const int N = 1e5+10;
priority_queue q; // 小根堆
int idx, w[N s;
while (m --) {
cin >> u >> v >> c;
add (u, v, c);
}
q.push ({0, s}); // 加入初始节点
d[s] = 0; // 到s的距离初始化为0
while (!q.empty ()) {
auto tp = q.top ();
q.pop ();
int dis = tp.x, from = tp.y;
if (dis != d[from]) continue;
/*下面的几句话实现的是刷新某点到起点s的最短距离,但是刷新前的点的信息依旧在队列里,我们得把它们弹出,判断哪些是失效的信息的标准就是比较 通过已刷新的数组d去访问此点到起点s的距离 与 通过队列里的first去访问此点到s点的距离,相等说明没刷新,不相等说明刷新了,你已经没用了,可以弹出了,因为我们已经保存了最新信息。
再说简单点,刷新之后的某点对应的d值应该是要等于tp.first的,不等于的话,说明d更新了,tp.first没更新,信息失效,弹出。
*/
for (int i = h[from]; ~i;i = ne[i]) {
int to = e[i];
if (d[to] > dis + w[i])
d[to] = dis + w[i],
q.push ({d[to], to});
}
}
for (int i = 1;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【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脚手架写一个简单的页面?