堆优化版的Dijkstra

适合稀疏图
邻接表存储

//堆优化的Dijkstra
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
int h[N],e[N],ne[N],w[N],idx;
int d[N],s[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 Dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(d, 0x3f, sizeof d);
    d[1]=0;
    heap.push({0,1});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        int ver=t.second, distance=t.first;
        s[ver]=true;

        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j] > distance+w[i])
            {
                d[j]=distance+w[i];
                heap.push({d[j],j});
            }
        }
    }

    if(d[n]==0x3f3f3f3f) return -1;
    else return d[n];
}


int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d", &x, &y, &z);
        add(x,y,z);
    }

    cout<<Dijkstra()<<endl;

    return 0;
}