#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <utility>


const int N=100005;
typedef long long ll;
ll dis[N];
bool vis[N];
int head[5*N],to[5*N],next[5*N];
ll W[2*N];
int cnt=-1;
int n,m,s;
const long long inf=2147483647;


std::priority_queue <std::pair<int,int>,std::vector<std::pair<int,int>>,std::greater<std::pair<int,int>>> pq;
void add(int u,int v,int w){
	next[++cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
	W[cnt]=w;
}

int main(){
	memset(head,-1,sizeof(head));
	scanf("%d %d %d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		int u,v,w;scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
	}
	for(int i=1;i<=n;i++) dis[i]=inf;
	dis[s]=0;
	pq.push({0,s});
	while(!pq.empty()){
		std::pair<int,int> t=pq.top();
		pq.pop();
		if(vis[t.second]) continue;
		vis[t.second]=1;
		for(int i=head[t.second];~i;i=next[i]){
			int v=to[i];
			if((dis[t.second]+W[i]<dis[v])&&!vis[v]){
			      dis[v]=dis[t.second]+W[i];
			      pq.push({dis[v],v});
			}
		}
		
	}
	for(int i=1;i<=n;i++){
		printf("%lld ", std::min(dis[i], (1LL<<31)-1));
	}
	return 0;
}

看了下题解,一直没看出和这个有什么差别，我要红温了