## 当然这个模板很早之前就过了
### 但是我还是想写个dijkstra+堆优化的模板
首先我们得了解一下dijkstra
他是一个o(n^2)的算法
首先每次找到dis最小的并且没有被访问过的点
然后访问所有的边更新最小值
然后我们发现其实dijkstra是非常慢的
然后就很多题目用不了
因为许多题目的点数都是10^5级别的
然后就只能使用SPFA算法
但是SPFA又容易被卡怎么办呢？
既然dijkstra是每次寻找dis最小的那个节点
为什么我们不把dis存储起来呢？
所以我们可以将dis和序号一起丢到堆里然后每次取堆顶
然后进行正常的dijkstra操作就行了
```cpp
#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;
}
```