dijkstra算法（堆优化）：
朴素版dijkstra算法的时间复杂度只和节点数量有关系，且时间复杂度为O(n^2)。当处理边很多的稠密图的时候，朴素版dijkstra算法没有问题。但是当遇到边很少的情况（稀疏图）时，时间开销有点过大了，因为朴素版的方法是建立一个二维数组，存储从一个点到另一个点是否存在边。当处理稀疏图时，由于边很少甚至有可能只有一条两条，所以绝大部分空间会被浪费。所以这个时候使用邻接矩阵并不合适，为此我们引入邻接表进行处理。邻接表就是建立一个用来存储链表的数组，每个链表的头节点就是起点，后面就是他指向的点。
dijkstra三部曲：1.找到源点到哪个点距离最近而且这个节点没有被访问过；2.将该节点标记为访问过；3.更新未访问节点到源点的距离。
卡码网：47.参加科学大会
题目链接：47. 参加科学大会（第六期模拟笔试）
思路：关于从边的角度怎么处理三部曲，我们可以把带权值的边存入小顶堆，因为小顶堆可以实现自动排序，这样我们在从小顶堆取元素时取出的就是距离源点最近的的节点所在的边。除此之外我们在往链表中存储元素时，存储的是节点和权值的键值对，即pair<int,int>。
代码：
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std;class mycomparison{public:bool operator()(const pair<int,int> &lhs, const pair<int,int> &rhs){//lhs表示左边的点 rhs表示右边的点return lhs.second > rhs.second;}
};struct Edge{int to;int val;//构造函数Edge(int t,int w): to(t),val(w){};//初始化列表
};int main(){int n,m,p1,p2,val;cin>>n>>m;//点数和边数vector<list<Edge>> grid(n+1);//链表里存的是Edge结构体for(int i=0;i<m;i++){cin>>p1>>p2>>val; //p1源点 p2终点grid[p1].push_back(Edge(p2,val));}int start = 1;int end = n;vector<int> minDist(n+1,INT_MAX);//存储源点到各个点的最大距离 初始化为最大值vector<bool> visited(n+1, false);//标记某个节点是否被访问过//优先级队列， 距离最小的节点在最上面 数据存入pair数组priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison> pq;pq.push(pair<int,int>(start,0));//到源点距离为0minDist[start]=0;while(!pq.empty()){//寻找距离源点最近的未访问的节点pair<int,int> cur = pq.top();//cur表示当前距离最近的节点pq.pop();if(visited[cur.first]) continue;//如果节点被访问过就跳过visited[cur.first]=true;//将当前访问的节点标记为true//更新未访问节点到当前节点的距离for(Edge edge : grid[cur.first]){//遍历当前节点为源点的所有边if(!visited[edge.to] && minDist[cur.first] + edge.val <minDist[edge.to]){minDist[edge.to] = minDist[cur.first] + edge.val;//将更新后的距离加入优先级队列pq.push(pair<int, int>(edge.to, minDist[edge.to]));}}}if(minDist[end] == INT_MAX) cout<<-1<<endl; //到达不了终点else cout<<minDist[end]<<endl;return 0;
}
