dijkstra 36分 求调

#include<bits/stdc++.h>
using namespace std;
int read() {
	int nn=0,mm=1;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-') {
			mm=-1;
		}
		ch=getchar();
	}
	while(ch<='9'&&ch>='0') {
		nn=nn*10+ch-'0';
		ch=getchar();
	}
	return nn*mm;
}
struct bian{
	int next;
	int len;
	int to;
} a[200001];
struct dian{
	int dis;
	int i;
	bool operator <(const dian &x)const{
        return x.dis<dis;
    }
};
int dis[100001],head[100001];
bool vis[100001];
int n,m,k;
priority_queue<dian>q;
void dijkstra() {
	for(int i=1; i<=n; i++) dis[i]=INT_MAX;
	dis[k]=0;
	while(!q.empty()){
		int now=q.top().i;
		q.pop();
		if(vis[now]){
			continue;
		}
		vis[now]=1;
		for(int i=head[now];i;i=a[i].next){
			int y=a[i].to;
			if(dis[y]>dis[now]+a[i].len) {
				dis[y]=dis[now]+a[i].len;
				if(!vis[y]){
					q.push({dis[y],y});
				}
			}
			
		}
	}
}
int main() {
	n=read(),m=read();
	k=read();
	for(int i=1;i<=m;i++){
		int s=read(),e=read(),len=read();
		a[i].next=head[s];
		a[i].len=len;
		a[i].to=e;
		head[s]=i;
	}
	q.push({0,k});
	dijkstra();
	for(int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}