下面是我的代码，dijkstra+堆优化：

cpp
#include<bits/stdc++.h>
#define rg register int 
using namespace std;
int n,m,h[100011],sum=0,l=0,dis[100011],st,d;
bool bj[100011];
struct node
{
	int to,nxt,s;
}a[400011];
struct nood
{
	int zz,w;
}b[100011];
inline void add(int x,int y,int z)
{
	sum++;
	a[sum].to=y;
	a[sum].nxt=h[x];
	a[sum].s=z;
	h[x]=sum;
}
inline void put(int x,int y)
{
	int net,now;
	l++;
	b[l].zz=x;
	b[l].w=y;
	now=l;
	while(now>1)
	{
		net=now/2;
		if(b[net].zz>=b[now].zz) return ;
		swap(b[net],b[now]);
		now=net; 
	} 
}
inline nood get()
{
	int net,now=1;
	nood k=b[1];
	b[1]=b[l--];
	while(now*2<=l)
	{
		net=now*2;
		if(net<l&&b[net].zz<b[net+1].zz) net++;
		if(b[now].zz>=b[net].zz) break;
		swap(b[now],b[net]);
		now=net; 
	} 
	return k;
}
int main()
{
	scanf("%d%d%d",&n,&m,&st);
	for(rg i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z); 
	} 
	dis[st]=0;
	d=h[st];
	bj[st]=1;
	do
	{
		dis[a[d].to]=a[d].s;
		put(a[d].s,a[d].to);
		d=a[d].nxt; 
	}
	while(d!=0);
	for(rg i=1;i<n;i++)
	{
		nood q=get();
		bj[q.w]=1;
		d=h[q.w];
		do
		{
			if(dis[a[d].to]>q.zz+a[d].s) dis[a[d].to]=q.zz+a[d].s;
			d=a[d].nxt;
		} 
		while(d!=0); 
	}
	for(rg i=1;i<=n;i++)
	{
		printf("%d ",dis[i]);
	} 
	return 0;
 }