优先队列
heap 堆 先进先出
队列里面的类型是pair,先比较第一个元素,第一个相同比较第二个
#include<queue>
//大的数排在前面 从大到小进行排列
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>> q;
//从小到大进行排列
#include<queue>
typedef pair<int,int> PII;
priority_queue<PII, vector<PII>, greater<PII>q;
堆优化的dijkstra
1.用于稠密图
2. 和朴素的dijstra 算法的区别是使用了优先队列
3. 时间复杂度(mlogn)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N = 150010;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool vis[N];
typedef pair<int,int> P;
int n;
// 堆优化dijkstra 用邻接表存图
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//优先队列
priority_queue<P,vector<P>, greater<P>>q;
q.push({0,1});
while(q.size()){
//找到最小的点
auto t = q.top();
q.pop();
int dis = t.first, ver = t.second;
if(vis[ver]) continue;
vis[ver] = true;
//进行更新
for(int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if((dist[j] > dis + w[i]) && !vis[j]){
dist[j] = dis + w[i];
q.push({dist[j], j});
}
}
}
// cout<<dist[n] << '\n';
if(dist[n] == 0x3f3f3f3f){
return -1;
}else return dist[n];
}
int main(){
int m;
cin>>n>>m;
memset(h, -1, sizeof h);
int x,y,z;
for(int i = 0; i < m; i++){
cin>>x>>y>>z;
add(x,y,z);
}
int ans = dijkstra();
cout<<ans<<'\n';
return 0;
}