玄关求条

#include <bits/stdc++.h>
#include <queue>
using namespace std;
int s,n,m,dis[100010],vis[100010];
struct edge {
	int v,w;
};
struct node {
	int id,d;
	bool operator<(const node &n)const {
		return d>n.d;
	}
};
vector<edge> E[100010];
priority_queue<node> q;
int main() {
	cin>>n>>m>>s;
	memset(dis,0x3f,sizeof(dis));
	for(int i=1; i<=m; i++) {
		int u,v,w;
		cin>>u>>v>>w;
		E[u].push_back({v,w});
		E[v].push_back({u,w});
	}
	dis[s]=0;
	q.push({s,0});
	while(!q.empty()) {
		node nd=q.top();
		q.pop();
		int id=nd.id,d=nd.d;
		if(vis[id]) continue;
		vis[id]=1;
		for(int i=0; i<E[id].size(); i++) {
			int v=E[id][i].v,w=E[id][i].w;
			if(!vis[v]&&dis[v]>d+w) {
				dis[v]=d+w;
				q.push({v,dis[v]});
			}
		}
	}
	for(int i=1; i<=n; i++) cout<<dis[i]<<" ";
	return 0;
}