Dijkstra 算法（非负边权单源最短路算法）模板

优先队列优化

题目链接

时间复杂度 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