算法竞赛改编的

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
const int N=1e6;
const int M=5e6;
typedef long long ll;
using namespace std;
struct edge{
	ll u,to;
	ll w;
	edge(ll a,ll b,ll c)
	{
		u=a,to=b,w=c;
	}
};
vector <edge> e[N];
struct node
{
	ll id,dis;
	node(ll a,ll b){
		id=a;dis=b;
	}
};
struct cmp
{
	
	bool operator()(node a,node b)
	{
		return a.dis>b.dis;
	}
};
ll m,n,pre[N],s,dis[N];
bool done[N];
void dijkstra(ll s)
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	priority_queue<node,vector<node>,cmp> q;
	q.push(node(s,dis[s]));
	while(!q.empty())
	{
		node u=q.top();
		q.pop();
		if(done[u.id])continue;
		done[u.id]=true;
		for(ll i=0;i<e[u.id].size();i++)
		{
			edge y=e[u.id][i];
			if(done[y.to]) continue;
			if(dis[y.to]>y.w+u.dis);
			{
				dis[y.to]=y.w+u.dis;
				q.push(node(y.to,dis[y.to]));
				pre[y.to]=u.id;
			}
		}
	}
	
	
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&s);
	//for(ll i=1;i<=n;i++) e[i].clear();
	while(m--)
	{
		ll u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		e[u].push_back(edge(u,v,w));
	} 
	dijkstra(s);
	for(ll i=1;i<=n;i++)
	{
		printf("%lld ",dis[i]);
	}
	return 0;
}