code

//dis
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1e5+10,maxm=2e5+10;
int n,m,s,head[maxn],headnum=0,dist[maxn],vis[maxn];
struct nodee{int to,next,value;}e[maxm];
struct nodeq{
	int value,id;
	bool operator<(const nodeq &x)const{
		return value>x.value;
	}
};priority_queue<nodeq>q;
void pushq(int value,int id){
	nodeq x;x.value=value;x.id=id;
	q.push(x);
}
void edged(int from,int to,int value){
	e[++headnum].next=head[from];
	head[from]=headnum;
	e[headnum].value=value;
	e[headnum].to=to;
}
void distra(){
	memset(dist,0x3f,sizeof(dist));dist[s]=0;
	pushq(0,s);
	while(!q.empty()){
		int u=q.top().id;q.pop();
		if(vis[u])  continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if(dist[u]+e[i].value<dist[v]){
				dist[v]=dist[u]+e[i].value;
				pushq(v,dist[v]);
			}
		}
	}
	return;
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		edged(x,y,z);
	}
	distra();
	for(int i=1;i<=n;i++){
		printf("%d ",dist[i]);
	}
	return 0;
}

好久没打了，打了一遍又重构了一遍，还是过不了。