搜索与图论 Dijkstra求最短路（堆优化）
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 109。
输入样例：
3 31 2 22 3 11 3 4
输出样例：
3
朴素Dijkstra 时间复杂度为 O(n2)
适合计算稠密图的单源最短路，边数 m2 ~ n (边数的平方与点数是同一数量级)
int dijkstra(){ memset(d,0x3f,sizeof(d)); d[1]=0; //找到从起点到n个点的最短路，需要遍历n次. for(int i=0;i
堆优化Dijkstra 时间复杂度为 O(m*logn)
适合计算稀疏图的单源最短路，边数m~n (边数与点数是同一数量级且点数比较多，105)
#includeusing namespace std;const int N = 1000010;typedef pair PII;int n,m;int h[N],e[N],w[N],ne[N],idx; //稀疏图使用邻接矩阵存储。int d[N],st[N];void add(int x,int y,int z){//w存储着点x到点y的权值。 e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;}int dijkstra(){ memset(d,0x3f,sizeof d); d[1]=0; priority_queue,greater > heap; //使用小根堆(优先队列)维护最短边。 heap.push({0,1}); //堆维护着起点到其余点的距离，从小到大排序 {距离,点}//循环使用距起点最近的点更新剩余点的距离。更新后的点和距离都入堆。 while(heap.size()) { PII t=heap.top(); heap.pop(); int ver=t.second,dis=t.first; //距离起点最近的点和距离。 if(st[ver]) continue; //如果t点最小值已经找到,跳过,避免重复边的重复更新。 st[ver]=1; //标记t点，t点的最近距离已经找到。 for(int i=h[ver];i!=-1;i=ne[i]) { int j=e[i]; if(d[j]>dis+w[i]) { d[j]=dis+w[i]; heap.push({d[j],j}); } } } if(d[n]==0x3f3f3f3f) return -1; return d[n];}int main(){ cin>>n>>m; memset(h,-1,sizeof h); while(m--) { int x,y,z; cin>>x>>y>>z; add(x,y,z); } cout<