dijkstra的堆优化-Toy模板网

这篇具有很好参考价值的文章主要介绍了dijkstra的堆优化。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

核心：priority_queue< pair<int,int> > 用优先队列来取最近的点，就不用遍历找点了

在pq中，是按pair的第一个元素（first）由大到小排序的，所以pair<距离，点号>，注意因为要的是最小值，所以距离要存负值
其实距离是纯纯的工具人，我们只是需要它来维持点的排序

每次取队首h，取出的就是dis最短的点
还要注意：
如果这个点的dis不等于h的dis，说明这个点在入队之后被更新了，那么我们就不用这个点了，直接continue；
因为后面会有个h2点比h1的dis更小，用h1更新就没有意义了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int> 

const int maxn=2e5;
int head[maxn],cnt;
ll dis[maxn];
int n,m,s;

struct node{
	int to,nxt;
	ll val;
}e[maxn];

void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].val=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;	
}

void dijkstra(int s){
	priority_queue<pii> q;
	memset(dis,0x3f3f,sizeof dis);
	q.push({0,s});
	dis[s]=0;
	while(!q.empty())
	{
		int dh=q.top().first;
		int h=q.top().second;
		q.pop();
		if(dh+dis[h]) continue;            //dh是负的，如果不相等就跳过
		for(int i=head[h];i;i=e[i].nxt)
		{
			int t=e[i].to;
			if(dis[t]>dis[h]+e[i].val)
			{
				dis[t]=dis[h]+e[i].val;
				q.push({-dis[t],t});        //注意因为要从小到大排序，所以要存负距离
			}
		}
	}
	for(int i=1;i<=n;i++)  cout<<dis[i]<<" ";
}

int main(){
	cin>>n>>m>>s;
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dijkstra(s);
	return 0;
}

注意pq和pair的用法

pq队首是pq.top()

pair首元素是x.first，尾元素是x.second，没有括号

补充一下其他东西，当我们需要重新写一个新的向前星时，我们可以用

        memset(head,0,sizeof head);
        cnt=0;

来删去原来的边（重置head和cnt就行）

重载priority_queue

priority_queue<pii,vector<pii>,greater<pii> >文章来源地址https://www.toymoban.com/news/detail-485596.html

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int> 
 
const int maxn=2e5;
int head[maxn],cnt;
ll dis[maxn];
int n,m,s;
 
struct node{
	int to,nxt;
	ll val;
}e[maxn];
 
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].val=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;	
}
 
void dijkstra(int s){
	priority_queue<pii,vector<pii>,greater<pii> > q;
	memset(dis,0x3f3f,sizeof dis);
	q.push({0,s});
	dis[s]=0;
	while(!q.empty())
	{
		int dh=q.top().first;
		int h=q.top().second;
		q.pop();
		if(dh-dis[h]) continue;            
		for(int i=head[h];i;i=e[i].nxt)
		{
			int t=e[i].to;
			if(dis[t]>dis[h]+e[i].val)
			{
				dis[t]=dis[h]+e[i].val;
				q.push({dis[t],t});        //注意因为要从小到大排序，所以要存负距离
			}
		}
	}
	for(int i=1;i<=n;i++)  cout<<dis[i]<<" ";
}
 
int main(){
	cin>>n>>m>>s;
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dijkstra(s);
	return 0;
}

到了这里，关于dijkstra的堆优化的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！