dij+堆

#include<cstdio>
#include<queue>
using namespace std;int l[100001],tot,dis[100001],s,n,m;
inline int read()//输入优化
{
int d=1,f=0;char c;
while(c=getchar(),c<48||c>57)if(c=='-')d=-1;f=(f<<3)+(f<<1)+c-48;
while(c=getchar(),c>47&&c<58) f=(f<<3)+(f<<1)+c-48;
return d*f;
}
struct node{int next,to,w;}e[500001];//边
struct heap{int u,d;};//堆
inline bool operator <(heap x,heap y){return x.d>y.d;}//小的在前面
inline void add(register int u,register int v,register int w){e[++tot]=(node){l[u],v,w};l[u]=tot;}//建边
bool vis[100001];//判断会不会重新走过。。。
inline void Dijstra_heap()
{
for(register int i=0;i<=n;i++) dis[i]=2147483647;
dis[s]=0;
priority_queue<heap>q;
q.push((heap){s,0});vis[s]=true;
while(q.size())
{
heap u=q.top();q.pop();//取出堆顶
int x=u.u,d=u.d;vis[x]=true;//标记
for(register int i=l[x];i;i=e[i].next)//用其进行拓展
{
int y=e[i].to,w=e[i].w;
if(dis[x]+w<dis[y])
{
dis[y]=dis[x]+w;//转移
if(!vis[y]) q.push((heap){y,dis[y]}),vis[y]=true;//没有标记过则标记并放入
}
}
vis[x]=false;//记得取消标记（没有也可以）
}
return;
}
signed main()
{
n=read();m=read();s=read();
for(register int i=1,x,y,z;i<=m;i++) x=read(),y=read(),z=read(),add(x,y,z);//输入
Dijstra_heap();//dij
for(register int i=1;i<=n;i++) printf("%d ",dis[i]);//输出
}