基本思路:
1、在dis数组里挑选一个离起点最近的点
2、用这个点更新其他点到起点的距离(松弛)
时间复杂度? Θ(mlogn)\Theta(m\log n)Θ(mlogn)
优先队列
啊但是,最后一行这么写不太对劲,Node 咋排才是默认小呢?所以我们需要一个这个
注意:1、在这个时候,priority_queue<node,vector<node>,greater<node>> pq;//默认小 就直接可以变成priority_queue <node> pq;
2、符号是反的
3、不能重载 >
dij代码示例