您当前的位置: 首页 >  算法

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

Dijkstra 算法(非负边权单源最短路算法)模板

不牌不改 发布时间:2022-03-13 17:42:57 ,浏览量:0

优先队列优化

题目链接

时间复杂度 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             
关注
打赏
1662186765
查看更多评论
0.0437s