dij模板[自用]

今天在学计划书，发现自己以前编的板子丑丑长长的，改得舒服一点当作新的板子唔..

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
int cnt=0,n,m,s,dis[maxn],vis[maxn],head[maxn];
struct Edge{
    int to,w,nex;
}edge[maxn];
struct lys
{
    int id,d;
    bool operator > (const lys tmp)const{
        return d>tmp.d;
    }
};
void add(int a,int b,int val)
{
    cnt++;edge[cnt].to=b;edge[cnt].w=val;
    edge[cnt].nex=head[a];head[a]=cnt;
}
priority_queue<lys,vector<lys>,greater<lys> > q;
void dij(int s)
{
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;
    q.push((lys){s,0});
    while(!q.empty())
    {
        lys tmp=q.top();
        q.pop();
        if(vis[tmp.id]){continue;}
        vis[tmp.id]=1;
        for(int i=head[tmp.id];i;i=edge[i].nex)
        {
            if(dis[edge[i].to]>dis[tmp.id]+edge[i].w)
             {
                  dis[edge[i].to]=dis[tmp.id]+edge[i].w;
                  q.push((lys){edge[i].to,dis[edge[i].to]});
             }
        }
    }
}
int main()
{  
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dij(s);
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
}