Dijkstra 90分 求调

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

const int maxn = 1e6+5;
const int maxe = 1e6+5;
const int inf=0x7f;
int n,m,s;

int dis[maxn];
int vis[maxn];

typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>> q;

struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++; //h[u] = 0; edge_cnt = 1;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }
    //返回head[u]
    int operator()(int u){ return h[u]; }
}g;

void init(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g.add(u,v,w);
    }
}

void dijkstra(){
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]==1) continue;
        vis[u]==1;
        for(int i=g(u);~i;i=g[i].next){
            int v=g[i].v;
            int w=g[i].w;
            if(vis[v]==0&&dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                q.push(make_pair(dis[v],v));
            }
        }
    }

}

int main(){
    init();
    memset(dis,inf,sizeof(dis));
    dijkstra();
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    return 0;
}