堆优化版Dijkstra模板

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <climits>
 5 #include <queue>
 6 using namespace std;
 7 
 8 typedef pair<int, int> PII;
 9 const int N = 150010;
10 int h[N], e[N], ne[N], w[N], dist[N];
11 int n, m, idx;
12 bool vis[N];
13 
14 void add(int a, int b, int c){
15     e[idx] = b;
16     ne[idx] = h[a];
17     w[idx] = c;
18     h[a] = idx ++;
19 }
20 int dijkstra(){
21     //将每个点的距离初始化为正无穷
22     memset(dist, 0x3f, sizeof dist);
23     
24     dist[1] = 0;
25     //声明一个优先队列
26     priority_queue<PII, vector<PII>, greater<PII> > heap;
27     heap.push({0, 1});
28     while(heap.size()){
29         auto t = heap.top();
30         heap.pop();
31         int ver = t.second, distance = t.first;
32         if(vis[ver]) continue; //判断这个点是否已经优化过其他点
33         vis[ver] = true;
34         for(int i = h[ver]; i != -1; i = ne[i]){
35             int j = e[i];
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) return -1;
43     return dist[n];
44 }
45 int main(){
46     memset(h, -1, sizeof h);
47     scanf("%d%d", &n, &m);
48     while(m --){
49         int a, b, c;
50         scanf("%d%d%d", &a, &b, &c);
51         add(a, b, c);
52     }
53     int t = dijkstra();
54     printf("%d\n", t);
55     
56     
57     return 0;
58 }