[Dijkstra+堆优化]

前言

欢迎来到CSP考前复习系列。。。。。。今天要讲的是Dijkstra。。。

当然，如果有任何错误的话，欢迎留言指出哟。。。

算法作用

Dijkstra算法用于解决单源最短路问题，即求取从一个给定的起点出发到其他节点的最短距离。

算法原理

我们首先定义一个数组$dis$，代表我们选定的起点到其他各个点的距离最小值。

然后，将$dis$数组中除了起点以外的所有的元素都赋成$inf$（无限大）。

然后开始扫描起点所连接的点，找出一个直接距离最短的点，加入已生成的树中，并将连接它们的这条边加入最小生成树中。

然后继续，从已有的最小生成树中的所有点出发，找到一个距离最近的，继续加入生成树。

算法结果

算法运行结束后，将会得到一个处理好的数组$dis$，其中$dis[i]$代表从起点出发到节点$i$的最短路长度。

算法实现
朴素方法
这个普通的写法我并不想过多介绍，因为这样做太过于普通，效率非常低。

你可以使用邻接矩阵来存储整个图，然后每次枚举对应的行或列来找到一个距离最近的。

代码也比较简单，这里并不想过多描述。事实上，我一开始就写的堆优化，因此再把它改成朴素算法将会比较多余。

堆优化
堆优化的主要思想就是使用一个优先队列（就是每次弹出的元素一定是整个队列中最小的元素）来代替最近距离的查找，用邻接表代替邻接矩阵，这样可以大幅度节约时间开销。

在这里有几个细节需要处理：

首先来讲，优先队列的数据类型应该是怎样的呢？
我们知道优先队列应该用于快速寻找距离最近的点。由于优先队列只是将最小的那个元素排在前面，因此我们应该定义一种数据类型，使得它包含该节点的编号以及该节点当前与起点的距离。

我们应该在什么时候对队列进行操作呢？
队列操作的地方，首先就是搜索刚开始，要为起点赋初始值，此时必须将起点加入优先队列中。该队列元素的节点编号为起点的编号，该节点当前与起点的距离为00。

那么如果一个节点到起点的最短距离通过其他的运算流程发生了变化，那么如何处理队列中的那个已经存入的元素？
事实上，你不需要理会队列中的元素，而是再存入一个就行了。因为如果要发生变化，只能将节点与起点之间的距离变得更小，而优先队列恰好是先让最小的那个弹出。

因此，轮到某一个队列元素弹出的时候，如果有多个元素的节点编号相同，那么被弹出的一定是节点编号最小的一个。等到后面再遇到这个节点编号的时候，我们只需要将它忽略掉就行了。

注意：$dijkstra$不能跑有负环的图和最长路(最长路的贪心是错的，自己手玩一下就好)

 1 #include <cstdio>
 2 #include <queue>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 int n,m,s;
 7 int head[100001],dis[100001],cnt;
 8 bool vis[100001];
 9 struct qwq{
10     int from,to,next;
11     long long len;
12 }edge[200001];
13 void add(int u,int v,int w)
14 {
15     cnt++;
16     edge[cnt].from=u;
17     edge[cnt].to=v;
18     edge[cnt].len=w;
19     edge[cnt].next=head[u];
20     head[u]=cnt;
21     return;
22 }
23 struct node{
24     int index,dist;
25     bool operator < (const node &x)const
26     {
27         return dist>x.dist;
28     }
29 };
30 priority_queue<node> q; 
31 int main()
32 {
33     scanf("%d%d%d",&n,&m,&s);
34     for(int i=1;i<=m;i++)
35     {
36         int u,v,w;
37         scanf("%d%d%d",&u,&v,&w);
38         add(u,v,w);
39     }
40     for(int i=1;i<=n;i++)
41     dis[i]=2147483647;
42     dis[s]=0;
43     q.push(node{s,0});
44     while(!q.empty())
45     {
46         node x=q.top();
47         q.pop();
48         int u=x.index;
49         if(vis[u]) continue;
50         vis[u]=1;
51         for(int i=head[u];i;i=edge[i].next)
52         {
53             if(dis[edge[i].to]>dis[u]+edge[i].len)
54             {
55                 dis[edge[i].to]=dis[u]+edge[i].len;
56                 q.push(node{edge[i].to,dis[edge[i].to]});
57             }
58         }
59     }
60     for(int i=1;i<=n;i++)
61     printf("%d ",dis[i]);
62     return 0;
63 }