当然这个模板很早之前就过了

但是我还是想写个dijkstra+堆优化的模板

首先我们得了解一下dijkstra

他是一个o(n^2)的算法

首先每次找到dis最小的并且没有被访问过的点

然后访问所有的边更新最小值

然后我们发现其实dijkstra是非常慢的

然后就很多题目用不了

因为许多题目的点数都是10^5级别的

然后就只能使用SPFA算法

但是SPFA又容易被卡怎么办呢?

既然dijkstra是每次寻找dis最小的那个节点

为什么我们不把dis存储起来呢?

所以我们可以将dis和序号一起丢到堆里然后每次取堆顶

然后进行正常的dijkstra操作就行了

#include<cstdio>
#include<queue>
using namespace std;
#define MAXN 2147483647
#define pa pair<long long,long long>
#define travel(a,b,c) for (register long long a=head[b],c=e[a].to;a!=0;a=e[a].next,c=e[a].to)

struct edge{
    long long to,val,next;
}e[500010];
long long n,m,s,len;
long long dis[10010],next[10010],head[10010];

inline long long v_in(){
    char ch=getchar();
    long long sum=0,f=1;
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        sum=(sum<<3)+(sum<<1)+(ch^48);
        ch=getchar();
    }
    return sum*f;
}//读入优化

inline void add(long long u,long long v,long long w){
    e[++len].to=v;
    e[len].val=w;
    e[len].next=head[u];
    head[u]=len;
}//添加有向边

int main(){
    n=v_in();
    m=v_in();
    s=v_in();
    for (register long long i=1;i<=m;i++){
        long long u=v_in(),v=v_in(),w=v_in();
        add(u,v,w);
    }//读入
    for (register long long i=1;i<=n;i++) dis[i]=MAXN;
    dis[s]=0;//dis初始化
    priority_queue<pa,vector<pa >,greater<pa > >q;
    q.push(make_pair(0,s));//起点入堆
    while (!q.empty()){
        long long u=q.top().second;
        q.pop();
        travel(i,u,v)//遍历每条边
            if (dis[v]>dis[u]+e[i].val){//更新
                dis[v]=dis[u]+e[i].val;
                q.push(make_pair(dis[v],v));
                //如果更新了就入堆
            }//所以其实我觉得和SPFA没有啥差别=.=
    }
    for (register long long i=1;i<=n;i++)
        printf("%lld ",dis[i]);
    putchar('\n');//输出
    return 0;
}