用的 $dijkstra$。

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
struct Node
{
	int dis;
	int next;
	int to;
}e[N];
int n,m,s,ans[N],head[N],cnt;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
bool vis[N];

void add(int x,int y,int z)
{
	e[++cnt]=(Node){y,head[x],z};
	head[x]=cnt;
	return ;
}

void dijkstra()
{
	pq.push(make_pair(0,s));
	while(pq.empty()==false)
	{
		pair<int,int>tmp=pq.top();
		pq.pop();
		int a=tmp.first,b=tmp.second;
		if(vis[a]==true)
			continue;
		vis[a]=true;
		for(int i=head[b];i>0;i=e[i].next)
		{
			int c=e[i].to;
			if(ans[c]>ans[b]+e[i].dis)
			{
				ans[c]=ans[b]+e[i].dis;
				pq.push(make_pair(ans[c],c));
			}
		}
	}
	return ;
}

int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
		ans[i]=INT_MAX;
	ans[s]=0;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dijkstra();
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	return 0;
}

码风不喜勿喷