堆优化版dijkstra
一：使用范围
单源最短路，所有边权都是正数，稀疏图（边数和点数相差不大），时间复杂度（mlogn);
二：优化思路
朴素版dijkstra 遍历所有点比较找出距离最近的点使用优先队列进行优化；
稀疏图用邻接表存图；
1.将优先队列定义成小根堆 priority_queue<PII,vector<PII>,greater<PII>> heap;
2.源点距离初始化为0，插入优先队列，从该点开始扩展； heap.push({0,1});
3.队头元素t保存到一个临时变量ver中，并将队头元素出队；
4.更新该点的到源点的最短距离
由于有重边的原因，可能有冗余项。由于是小根堆，最短的距离会先出队，再进行标记，下次遇到已标记的continue;
代码附上。
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 typedef pair<int,int>PII; 6 const int N=150010; 7 int h[N],e[N],w[N],nex[N],idx; 8 int dist[N]; 9 bool str[N]; 10 int n,m; 11 void add(int a,int b,int c) 12 { 13 e[idx]=b;w[idx]=c;nex[idx]=h[a];h[a]=idx++; 14 } 15 int dijkstra() 16 { 17 memset(dist,0x3f,sizeof dist); 18 dist[0]=1; 19 priority_queue<PII,vector<PII>,greater<PII>> heap; 20 heap.push({0,1}); 21 while(heap.size()) 22 { 23 auto t=heap.top(); 24 heap.pop(); 25 int ver=t.second,distance=t.first; 26 if(str[ver]) continue; 27 str[ver]=true; 28 for(int i=h[ver];i!=-1;i=nex[i]) 29 { 30 int j=e[i]; 31 if(dist[j]>distance+w[i]) 32 { 33 dist[j]=distance+w[i]; 34 heap.push({dist[j],j}); 35 } 36 } 37 } 38 if(dist[n]==0x3f3f3f3f) return -1; 39 return dist[n]; 40 } 41 int main() 42 { 43 cin>>n>>m; 44 memset(h,-1,sizeof h); 45 while(m--) 46 { 47 int x,y,z; 48 cin>>x>>y>>z; 49 add(x,y,z); 50 } 51 int k=dijkstra(); 52 cout<<k<<endl; 53 return 0; 54 }