3.2.2 最短路径 堆优化版Djkstra算法
堆优化版 Dijkstra算法
Dijkstra优化方法：
小根堆存储1号点到可以到达的每个节点的最短路径，直至拓展到n号点
例题 AcWing 850.Dijkstra求最短路 II
题目大意:
给定一个n 个点m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。求 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 − 1 。
数据范围：
1 ≤ n , m ≤ 1.5×10^5
0 ≤ e ≤ 10000
e 是边长。
思路：
节点个数和边的个数相差不多，为稀疏图，使用邻接表存储，并用堆优化版Dijkstra算法计算最短路径
Solved：
#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define fi first
#define se secondusing namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;//邻接表
int h[N],e[N],w[N],ne[N],idx;int dist[N];//存储最短路径
int st[N];//确定是否最短
int n,m;//图的加边
void add(int x,int y,int z){e[idx]=y,w[idx]=z;ne[idx]=h[x];h[x]=idx++;
}int Djkstra()
{//初始化distmemset(dist,0x3f,sizeof(dist));dist[1]=0;//堆优化Dijkstra//first:距离 second:节点编号priority_queue<PII,vector<PII>,greater<PII>> q;q.push({0,1});while(!q.empty()){auto t=q.top();q.pop();//ver:点编号 dis:距离int ver=t.se,dis=t.fi;for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];//j:下个点编号//如果1号点走该较短路径 到达下个目标点之间距离//小于下个点与1号点之间距离，更新dist[下个点],qif(dis+w[i]<dist[j]){dist[j]=dis+w[i];q.push({dist[j],j});}}}if(dist[n]==INF) return -1;return dist[n];
}signed main()
{//初始化邻接表memset(h,-1,sizeof(h));cin>>n>>m;while(m--){int x,y,z;cin>>x>>y>>z;add(x,y,z);}cout<<Djkstra()<<endl;return 0;
}