dij求教20分

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define maxn 100001
#define INF 100000001
using namespace std;
int n,m,s;
vector <int > g[maxn],w[maxn];
bool vis[maxn];
int dis[maxn];
void dijkstra(){
	priority_queue<int,vector<int>,greater<int> > q;
	for (int i = 1;i <= n;++i)dis[i] = INF;
	dis[s] = 0;q.push(s);
	while (!q.empty()){
		int u = q.top();
		int cnt = g[u].size();
		q.pop();
		if (vis[u] == 1)continue;
		vis[u] = 1;
		for (int i = 0;i < cnt; ++i){
			int v = g[u][i],val = w[u][i];
			if (dis[v] > dis[u] + val){
				dis[v] = dis[u] + val;
				if (!vis[v]){
					q.push(v);
				}
			}
		}
	}
}
signed main(){
	ios :: sync_with_stdio(false);
	cin >> n >> m >> s;
	for (int i = 1;i <= m; ++i){
		int u,v,c;
		cin >> u >> v >> c;
		g[u].push_back(v);w[u].push_back(c); 
	}
	dijkstra();
	for (int i = 1;i <= n; ++i){
		cout <<dis[i]<<' ';
	}
}