9.Dijkstra求最短路 II 堆优化的Dijkstra

堆优化版的Dijkstra算法

稀疏图

找最小距离这一步是最慢的，在一堆数中找一个最小的数，所以可以用堆优化，可以变为O(1)

用堆来存储，所有点到起点的最短距离

然后修改其他数的时间复杂度每次是log n，一共修改m次

这里的堆有两种实现方式

1.手写堆：好处：可以时时刻刻保证堆里面只有n个数，支持修改堆当中任意一个元素

　　　　　坏处：复杂难写

2.优先队列：好处：简单好写

　　　　　　坏处：不支持修改任意一个元素的操作，实现方式就是冗余

　　　　　　　　　每次修改就往队列里面插入一个新的数

　　　　　　　　　就造成了堆里面总的元素个数是m，时间复杂度变成m log m，但其实还是一个级别

所以堆优化版的Dijkstra直接用优先队列

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 //稀疏图用邻接表
 4 //用邻接表存的话，重边就无所谓了
 5 const int N = 150010;
 6 int h[N], e[N], w[N], ne[N], idx;
 7 //w是权重
 8 int n, m;
 9 bool st[N];
10 int dist[N];
11 typedef pair<int, int> PII;
12 void add(int a, int b, int c) {
13     e[idx] = b;
14     w[idx] = c;
15     ne[idx] = h[a];
16     h[a] = idx++;
17 }
18 int dijkstra() {
19     memset(dist, 0x3f, sizeof dist);
20     priority_queue<PII, vector<PII>, greater<PII> > heap;
21     //堆里面存的是pair
22     dist[1] = 0;
23     heap.push({0, 1});
24     //first是距离，second是编号
25     while (heap.size()) {
26         PII t = heap.top();
27         heap.pop();
28         int ver = t.second; //ver是节点编号
29         int distance = t.first; //距离
30         if (st[ver]) {
31             continue;
32         }
33         st[ver] = true;
34         for (int i = h[ver]; i != -1; i = ne[i]) { //用当前这个点更新其他点
35             int j = e[i]; //j存储编号
36             if (dist[j] > distance + w[i]) {
37                 dist[j] = distance + w[i];
38                 heap.push({dist[j], j});
39             }
40         }
41     }
42     if (dist[n] == 0x3f3f3f3f) {
43         return -1;
44     } 
45     return dist[n];
46 }
47 int main() {
48     memset(h, -1, sizeof h);
49     cin >> n >> m;
50     while (m--) {
51         int a, b, c;
52         cin >> a >> b >> c;
53         add(a, b, c);
54     }
55     int t = dijkstra();
56     if (t == -1) {
57         cout << -1 << endl;
58     } else {
59         cout << t << endl;
60     }
61     return 0;
62 }