可爱猫娘玄关求条52pts的dijkstra喵

//喵~~~~~~~~~~~~~
#include<bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
using namespace std;

int n,m,s;
vector<pair<int,int> > e[100005];
bool vis[100005];
int dis[100005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;

void dij(){
	q.push(mp(0,s));
	dis[s]=0;
	while(q.size()){
		int u=q.top().s;
		q.pop();
		if(vis[u]){
			continue;
		}
		vis[u]=1;
		for(auto v:e[u]){
			if(vis[v.s]){
				continue;
			}
			if(dis[v.s]>dis[u]+v.f){
				dis[v.s]=dis[u]+v.f;
				q.push(mp(v.f+1,v.s));
			}			
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back(mp(w,v));
	}
	memset(dis,0x3f,sizeof(dis));
	dij();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
	return 0;
}