又是好久没有写题解了。。。。。
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;
}
代码的解释已经在注释中给出了，如果有不明白欢迎私信我!
内容来源于网络如有侵权请私信删除
文章来源: 博客园
原文链接: https://www.cnblogs.com/Warframe-Gauss/p/13387717.html
- 还没有人评论，欢迎说说您的想法！
客服
