最短路径----Dijstra堆优化

单源最短路径(是速度最快且最稳定的算法，但不过只能求带有非负权图)

思路：

Dijstra每次需要遍历所有的点，找到一个最小值，而堆优化则是利用小顶堆的优势，每次都将距离最短的点都放在队列的顶部，则无需每次遍历所有的点，这样所需的时间就更短。

时间复杂度O(mlogn)

Code:

#include<iostream>
#include<queue>
#include<memory.h>
#include<vector>
#define mp(x,y) make_pair(x,y)
using namespace std;
typedef pair<int,int> PP;
const int M=200005;
int tot,head[M],ver[M],edge[M],ne[M];//邻接表存图
int dis[M],vis[M];
int n,m,s;//顶点数，边数，起点
//priority_queue<PP> heap;//默认是为大顶堆
priority_queue<PP,vector<PP>,greater<PP> > heap;//创建小顶堆
void add(int x,int y,int z) 
{
    ver[++tot]=y;//终点数组
    edge[tot]=z;.//边权数组
    ne[tot]=head[x];//下一节点数组
    head[x]=tot;//头数组
}
void dijstra(int s)
{
    dis[s]=0;//起点到本身的距离为0
    heap.push(mp(0,s));//将起点存放到优先队列当中
    while(heap.size())
    {
        int x=heap.top().second;//读取优先队列中的点
        heap.pop();//取出刚刚读取的点
        if(vis[x]) continue;//如果这个点以及读取过 就跳过
        vis[x]=1;//标记刚刚读取的点
        for(int i=head[x];i;i=ne[i])//遍历图
        {
            int y=ver[i];
            int w=edge[i];
            if(dis[y]>dis[x]+w)//判断是否有更近的距离
            {
                dis[y]=dis[x]+w;//更新起点到y点的距离
                heap.push(mp(dis[y],y));//存放到队列当中        
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w); //连接表存图
    }
    memset(vis,0,sizeof(vis));//初始化vis
//    memset(dis,0x3f,sizeof(dis));//初始化dis
    for(int i=1;i<=n;i++)
    dis[i]=2147483647;
    dijstra(s);
    for(int i=1;i<=n;i++)
    cout<<dis[i]<<' ';//输出起点到各个点的距离
    return 0;
}