#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdarg.h>
typedef long long ll;
ll n,m,s,ui,vi,wi,head[100005],cnt,lenth,vis[100005],dis[100005],tree[500005];
typedef struct
{
	ll to,len,next;
}hh;
hh edge[500005];
void swap(ll *w,ll *l)
{
	int k;k=*w;*w=*l;*l=k;
}
void add(ll w,ll l,ll e)
{
	cnt++;
	edge[cnt].to=l;
	edge[cnt].len=e;
	edge[cnt].next=head[w];
	head[w]=cnt;
}
void push(ll w)
{
	lenth++;
	tree[lenth]=w;
	ll fa,son;
	son=lenth;
	while (son>1)
	{
		fa=son/2;
		if (dis[tree[fa]]<=dis[tree[son]])
			return;
		swap(tree+fa,tree+son);
		son=fa;
	}
}
ll get(void)
{
	ll r=tree[1];
	tree[1]=tree[lenth];
	lenth--;
	ll fa=1,son;
	while ((fa*2)<=lenth)
	{
		son=fa*2;
		if (((son+1)<=lenth)&&(dis[tree[son]]>dis[tree[son+1]]))
			son++;
		if (dis[tree[fa]]<=dis[tree[son]])
			break;
		swap(tree+fa,tree+son);
		fa=son;
	}
	return r;
}
int main(void)
{
	scanf("%lld%lld%lld",&n,&m,&s);
	for (ll x=1;x<=m;x++)
	{
		scanf("%lld%lld%lld",&ui,&vi,&wi);
		add(ui,vi,wi);
	}
	for (ll x=1;x<=n;x++)
		dis[x]=2147483647;
	vis[s]=1;dis[s]=0;push(s);
	for (ll x=1;x<=n;x++)
	{
		ll k=get();
		vis[k]=1;
		for (ll y=head[k];y;y=edge[y].next)
			if ((!vis[edge[y].to])&&dis[edge[y].to]>dis[k]+edge[y].len)
			{
				dis[edge[y].to]=dis[k]+edge[y].len;
				push(edge[y].to);
			}
	}
	for (ll x=1;x<=n;x++)
		printf("%lld ",dis[x]);
	return 0;
}

如题，只得了20分。