一、问题描述：
给定一个带权有向图G=(V,E) ，其中每条边的权是一个非负实数。再给定 V 中的一个顶点，称为源，计算源到所有顶点的最短距离。
实例：单源最短路径（弱化版）/problemnew/show/P3371
二、 求取过程：
1. 从起点开始，查找所有与起点直接相连的点，并把连接它们的边权值作为起点到它们的距离(有平行边取最小值)。起点到起点的距离为0，其它不与起点直接相连的点距离为无穷大，存入上图所示的表中。
2. 遍历所有点，查找得到的结果中距离最小的那个点，然后再看所有与该点直接相连的点，计算该点到它们的最短距离(即从起点开始，经由该点到达的点的距离)，根据结果更新上图。
3. 不断重复2中过程，直到每一个点都像2中那样计算过一遍。
觉得抽象的话可以看视频：/video/av2156069
三、合理性：
假设A到C经过B，如果最短路径经过B，那么此时A到B的路径必定最短。
对于第一次操作，我们已经确定了从起点直接到所有点的最短距离。
此时取距离的最小值，有两种情况，一种是最小值来自跳过中间点的直接路径，那么我们可知从起点到该点的最短距离一定来自该路径，因为所有中间点的距离已经比其大，标记该点，已经使用过，接下来该点连接的点也可以根据该点的距离来处理了，因为此时A到B的距离已经最短，且中间点也不会对再对该点产生影响。另一种是最小值来自某一中间路径，那么经过该点的操作，完全有可能使第一次操作得到的距离改变，这就是取最小值的意义。若在未确定某一点最短距离的情况下对该点进行处理，由于该点已经标记使用，那么后续即使该点最短距离改变了，也无法改变该点已经确定的点的情况了。
如图所示的情况，第一次操作后我们知道直接与1相连的点有2, 3, 4。
如果此时不取最小值，例如对4进行处理，那么5的距离直接被确定为10000，此时4被标记使用，后续我们即使通过2，3改变了4的最短距离，5的距离也无法进行改变了。
四、算法实现：
1. 单源最短路径（弱化版）/problemnew/show/P3371
首先要知道怎么建图：
#include<bits/stdc++.h>using namespace std;const int N=1e6+5;const int MAX=2147483647;struct node{ //建图(链式向前星，二维矩阵会炸)，储存边int from;int to;int value;int next;}edge[200005];int head[N]; int dis[N]; //记录每一个顶点的距离int visited[N]; //记录是否访问过某一个顶点int main(){int n,m,s;int cnt=0;scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=n;i++) dis[i]=MAX; //距离初始化为无穷大memset(head,0,sizeof(head)); //这两行其实可以不要memset(visited,0,sizeof(visited));for(int i=1;i<=m;i++) //建图，储存边{cnt++;scanf("%d%d%d",&edge[cnt].from,&edge[cnt].to,&edge[cnt].value);int from=edge[cnt].from;int to=edge[cnt].to;edge[cnt].next=head[from];head[from]=cnt;}int start=s; //以s为起点dis[start]=0; //起点到自己的距离为0while(visited[start]!=1) //开始模拟查找过程{visited[start]=1; //标记该起点，表示已访问过for(int i=head[start];i!=0;i=edge[i].next) //读取与起点相连的边{if(dis[edge[i].to]>dis[start]+edge[i].value) //算法的核心dis[edge[i].to]=dis[start]+edge[i].value;}int minn=MAX; //每一次都寻找所有点中距离最小的点for(int i=1;i<=n;i++){if(visited[i]!=1 && minn>dis[i]){minn=dis[i];start=i; //以距离最小的点为新的起点，开始查找}}}for(int i=1;i<=n;i++){if(i==n) printf("%d\n",dis[i]);else printf("%d ",dis[i]);}}
2.单源最短路径（标准版）：/problemnew/show/P4779
这题数据要比上一题大，所以要进行优化。
上一题的写法每一次都要查找距离最短的点，占用了大量时间，我们用优先队列优化这个过程。
有关优先队列可参考：/qq_19656301/article/details/82490601
#include <bits/stdc++.h>using namespace std;const int N=1e5+5;const int MAX=2147483647;typedef long long LL;struct node{ //建图部分还是一样的int from;int to;int value;int next;}edge[2*N];int head[N];LL dis[N];int visited[N];priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >vis; //优先队列int main(){int n,m,s;int cnt=0;cin>>n>>m>>s;for(int i=1;i<=n;i++) dis[i]=MAX;for(int i=1;i<=m;i++){cnt++;scanf("%d%d%d",&edge[cnt].from,&edge[cnt].to,&edge[cnt].value);edge[cnt].next=head[edge[cnt].from];head[edge[cnt].from]=cnt;}dis[s]=0;vis.push(make_pair(0,s)); //储存某点距离和该点//make_pair是c++自带的二元组定义方式,可以通过first、second访问第一个，第二个元素(小根堆以第一个值排序)while(!vis.empty()) //判断所有点是否都查找过一遍{int start=vis.top().second; //优先队列队首即最小的元素vis.pop();if(visited[start]==1) continue; //如果该点查找过，跳过visited[start]=1;for(int i=head[start];i!=0;i=edge[i].next){if(dis[edge[i].to]>dis[start]+edge[i].value){dis[edge[i].to]=dis[start]+edge[i].value;vis.push(make_pair(dis[edge[i].to],edge[i].to));}}}for(int i=1;i<=n;i++){if(i==n) printf("%d\n",dis[i]);else printf("%d ",dis[i]);}}
