洛谷P2299题解：Dijkstra+堆优化 – Warframe

又是好久没有写题解了。。。。。

1.题意分析：

P2299是一道非常经典的图论最短路练习题。

图论最短路是图论中非常重要的一个知识模块，其主要算法有Dijkstra，Bellman-Ford，SPFA和Floyd。在这片题解中我们着重介绍Dijkstra算法。

2.算法详解：

Dijkstra应该是各位在学习图论的时候耳熟能详的一种算法，也是Dijkstra带我走进了图论的大门。

Dijkstra算法的发明者是Edsger Wybe Dijkstra，请大家记住这个人，因为他是信息学领域的一位大拿。

他的另一项成就相信也有很多大佬知道，那就是“go to有害论”。

话说回来，我们再来仔细看看Dijkstra算法是怎样运行和实现的。

程序的逻辑如下：

• 维护两个集合，一直最短路径节点集合A和这些点向外扩散的邻居节点集合B。

• 把整张图的起点s放到A中，把s中所有邻居放到B中，这样的话邻居到s的距离就是直连距离。

• 从B中找出距离起点s最短的节点u，放到A中。

• 把节点u的所有新邻居放到B中，注意要将$u$的所有邻居都放进去。例如u有一个邻居v，那么v到s的距离dis(s,v)就是dis(s,u)+dis(u,v)

• 重复执行前面两步，直到B为空时结束。

3.算法代码实现：

我们这里讲解的代码是用一个优先队列(priority queue)来实现的，这样可以最大限度的优化时间。

先贴总代码（也就是这道题的）：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int tot=0;
int ner[200001],edge[200001],nxt[200001],head[200001],b[200001],dis[200001];
void add(int x,int y,int z)//使用邻接表，在这里加入边
{
	ner[++tot]=y;
	edge[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
}
priority_queue< pair<int,int> > q;//定义优先队列
inline bool read(LL &num)//快速读入，建议大家当做模板背牢
{
	char in;
	bool isn=false;
	in=getchar();
	if(in==EOF) return false;
	while(in!="-"&&(in<"0"||in>"9")) in=getchar();
	if(in=="-") {isn=true;num+=in-"0";}
	else num=in-"0";
	while(in=getchar(),in>="0"&&in<="9") {num*=10;num+=in-"0";}
	if(isn) num=-num;
	return true;
}
int main()
{
	LL n,m,i,x,y,z;
	read(n);
	read(m);
	for(i=1;i<=m;i++)
	{
		read(x);//使用快速读入读入起点终点和边权
		read(y);
		read(z);
		add(x,y,z);//因为是无向图，所以要加两次边
		add(y,x,z);
		if(x==1) dis[y]=z;//如果起点是x，那么直连y
	}
	memset(dis,0x7f7f7f7f,sizeof(dis));
	memset(b,0,sizeof(b));//非常必要的初始化
	dis[1]=0;
	q.push(make_pair(0,1));
	while(q.size())//这里的队列q模拟的是集合B，当B为空时跳出循环
	{
		int c=q.top().second;//找出队头
		q.pop();
		if(b[c]) continue;
		b[c]=1;
		for(int j=head[c];j;j=nxt[j])//循环遍历当前节点的邻居
	    	{
	        	y=ner[j];
			z=edge[j];
			if(z<0x7f7f7f7f)
            		{
                		if(dis[y]>dis[c]+z)//更新当前邻居到节点u的距离，在图论中我们称为“松弛”
                		{
                    			dis[y]=dis[c]+z;
                    			q.push(make_pair(-dis[y],y));
				}
            		}
        	}
	}
    	dis[1]=0;
    	printf("%d",dis[n]);//输出最终结果
	return 0;
}

代码的解释已经在注释中给出了，如果有不明白欢迎私信我!