Dijkstra【模板】

· · 算法·理论 

priority_queue<pair<int,int> > q; //第一维存相反数，使大根堆变小根堆 
void Dijkstra(){
    for(int i=1;i<=n;i++){
        dis[i]=2147483647;
    }
    dis[st]=0;
    q.push(make_pair(0,st));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(f[u]){
            continue;
        }
        f[u]=true;
        for(int i=head[u];i!=0;i=nex[i]){
            int v=ver[i],w=edge[i];
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
}