[编程笔记]-Dijkstra(HeapOptimized)迪杰斯特拉（堆优化）

概念

其实就是用堆来优化Dijkstra算法（废话）。由于O(logm)（STL）与O(logn)（手写）为同一数量级，所以还是推荐直接用STL里的优先队列了。

其实就是优化了找当前距离最短的点的过程嘛。

由于是稀疏图，所以要用链式前向星做了。

代码

事实上这种优化算法往往比朴素版更常见~

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

const int N=1.5e5+5;

int n,m;
int x,y,z;

int idk;
int hd[N],ne[N],to[N],ed[N];

void merge(int u,int v,int x){
    ed[++idk]=x;
    to[idk]=v;
    ne[idk]=hd[u];
    hd[u]=idk;
}

int dij(int be,int en){
    int dis[N];
    bool fns[N]={false};
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    dis[be]=0;
    pq.push({0,be});
    while(!pq.empty()){
        auto tp=pq.top();pq.pop();
        int ds=tp.first,dt=tp.second;
        if(fns[dt])continue;
        fns[dt]=true;
        if(dt==en)break;
        for(int i=hd[dt];i;i=ne[i]){
            if(dis[to[i]]>dis[dt]+ed[i]){
                dis[to[i]]=dis[dt]+ed[i];
                pq.push({dis[to[i]],to[i]});
            }
        }
    }
    if(dis[en]==0x3f3f3f3f)return -1;
    else return dis[en]; 
}

int main(){
    cin>>n>>m;
    while(m--){
        cin>>x>>y>>z;
        merge(x,y,z);
    }
    cout<<dij(1,n);
    return 0;
}

完结撒花o(￣︶￣)o