dijkstra-堆优化版
不知道几刷的心得体会:就是在朴素版的基础上使用优先队列对找到距离源点最近的点这一步作优化,但是只限于稀疏图(因为时间复杂度是 O(mlogm), 如果是稠密图则边数m和n^2属于同一个量级,时间复杂度变为O(n^2logm),得不偿失)
-
由于要用距离源点最近的点更新其他点到源点的距离,但是由于在优先队列中无法进行修改值的操作,因此只能把更新后的加入队列,这就造成了冗余,因此一定要判断
if(st[ver]) continue;
-
邻接表可以类比一个点发出的很多条射线,因此这个点a就要作为表头,即h[a] = idx,idx相当于是边的编号,作为一个中介去存储和a点相接的点、边权
注意:初始化邻接表memset(h, -1, sizeof h); -
优先队列的定义方法:
priority_queue<PII, vector<PII> greater<PII>>
,系统对存入的点进行排序 -
为什么要用pair存储点的数据呢:存到源点的距离无可厚非,因为要找距离源点最近的点;存这个点的编号则是因为要拿这个距离源点最近的点去更新和这个点相邻的其他点到源点的距离,在邻接表里,头结点的下标就是一个点的编号,因此要存!!!
-
无论是朴素版还是堆优化版的dijkstra, 都要初始化每个点到源点的距离为无穷大,然后再把源点到源点的距离置为0,在朴素版中(邻接矩阵),存数据前要初始化邻接矩阵为无穷大,后续直接存min(g[][], weight),即直接存最小的边;而在堆优化版的dijkstra中,由于遍历邻接表找可更新的距离的边,因此无需提前初始化为无穷大,反而要初始化表头为空,即memset(h, -1, sizeof -1)
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII; //{到源点距离,编号}
const int N = 1e6 + 10;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int d[N];
bool st[N];
int add(int x, int y, int z){ //idx是中介 代表第idx条边
e[idx] = y;
w[idx] = z;
ne[idx] = h[x];
h[x] = idx++;
}
int dijkstra(){
memset(d, 0x3f, sizeof d);
priority_queue<PII, vector<PII>, greater<PII>> heap; //构建大根堆
d[1] = 0;
heap.push({0, 1});
while(heap.size()){
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first; //由t找到距离源点最近的点,下面更新ver这个点相邻边到源点距离
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; ~i; i = ne[i]){
int j = e[i]; //找到邻接的边的点是多少
if(d[j] > distance + w[i]){
d[j] = distance + w[i];
heap.push({d[j], j});
}
}
}
if(d[n] == 0x3f3f3f3f) return -1;
else return d[n];
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++){
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
cout << dijkstra() << endl;
return 0;
}