【模板】——dijkstra（堆优化）

dijkstra（堆优化）模板

例题

#include
#include
#include
#include
#define inf 0x3f3f3f3f//无穷大 
using namespace std;
const int N=1e6;
int e[N*2],ne[N*2],h[N],cnt=0,w[N],dis[N],st[N]={0},s,m,n;
//w用于存储边的权值；dis存储每个点到源点的距离；st为状态数组，1表示当前点已找到最短路，0则相反
//s为初始点，m为边的数量，n为点的数量 
typedef pair pii;//first为到源点距离，second为节点编号 
priority_queue,greater >heap;//定义优先队列，注意greater后一定加一个空格 
//stl的优先队列默认为大根堆，加上greater后为小根堆 
void add(int a,int b,int c)//采取邻接表存储图 
{
	e[cnt]=b;
	ne[cnt]=h[a];
	w[cnt]=c;
	h[a]=cnt++;
	return ;
}
void dijkstra()//dijkstra算法主体 
{	
	memset(dis,0x3f,sizeof dis);//易漏，将dis清成无穷大 
	dis[s]=0;
	heap.push({0,s});
	while(!heap.empty())
	{
		pii t=heap.top();//优先队列与普通队列不同，访问队头用top 
		heap.pop();
		int y=t.second;
		if(st[y]==0)
		{
			st[y]=1;
			int v=t.first;
			for(int i=h[y];i!=-1;i=ne[i])
			{
				int j=e[i];
				dis[j]=min(dis[j],v+w[i]);//松弛操作 
				heap.push({dis[j],j});
			}
		}
	}
	return ; 
}
int main()
{
	memset(h,-1,sizeof h);//易漏，必须将链表“数组”清成-1 
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;//a->b 且 此边权值为c 
		cin>>a>>b>>c;
		add(a,b,c);
	}
	cin>>s;
	dijkstra();
	//最后，若一点到源点距离为inf，则此点与源点不连通，若不等于inf，则dis[该点编号]即为其到源点距离 
	return 0;
}

ps:转载自即使敌众我寡