dij+堆优化

定义：

因为dij是通过贪心实现的
所以
定义一个小根堆的优先队列
即：

priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > > que;

实现：

就一遍dij就ヾ(❀^ω^)ノﾞok了

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

int n,m,dis[1000005],head[1000005],cnt,minx,k,s;
bool vis[1000005];

priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > > que;

struct node{
    int next,w,u,v,s;
}edge[50000005];

inline void add_edge(int x,int y,int z){
    edge[++cnt].u=x;
    edge[cnt].v=y;
    edge[cnt].w=z;
    edge[cnt].next=head[x];
    head[x]=cnt;
}

inline void shuru(int x){
    int q,p,e;
    for(int i=1;i<=x;i++){
        cin>>q>>p>>e;
        add_edge(q,p,e);
    }
}

inline void chushihua(int x){
    for(int i=1;i<=n;i++){
        dis[i]=2147483647;
    }
    dis[x]=0;
}

inline void dij(int x){
    que.push(make_pair(dis[x],x));
    while(!que.empty()){
        pair<long long,int> t=que.top();
        que.pop();
        if(vis[t.second]==1) continue;
        for(int j=head[t.second];j!=0;j=edge[j].next){
            if(dis[edge[j].v]>dis[t.second]+edge[j].w){
                dis[edge[j].v]=dis[t.second]+edge[j].w;
                que.push(make_pair(dis[edge[j].v],edge[j].v));
            }
        }
    }
}

int main(){
    cin>>n>>m;
    shuru(m);
    chushihua(1);
    dij(1);
    if(dis[n]==2147483647)cout<<"-1"<<endl;
    else cout<<dis[n]<<endl;
    return 0;
}