68pts求条

#include <bits/stdc++.h>
using namespace std;
int head[202000], cnt, n, m, s;
long long dis[202000];
bool vis[202000];
struct Edge
{
	int to, dis;
	int next;
}edge[202000]; 
struct dot
{
	int id, dis;
	bool operator < (const dot & x) const
	{
		return x.dis < dis;
	}
};
void addline(int u, int v, int w)
{
	cnt++;
	edge[cnt].to = v;
	edge[cnt].dis = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
} 
priority_queue<dot> q;
void dijistra()
{
	while (!q.empty())
	{
		dot tmp = q.top();
		int num = tmp.id;
		q.pop();
		if (vis[num])	continue;
		else
		{
			vis[num] = 1;
			for (int i = head[num]; i; i = edge[i].next)
			{
				int e = edge[i].to;
				if (dis[e] > dis[num] + edge[i].dis)
				{
					dis[e] = dis[num] + edge[i].dis;
					if (!vis[e])
					{
						q.push((dot){e, dis[e]});
					}
				}
			}
		} 
	}
}
int main()
{
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		addline(u, v, w);
	}
	for (int i = 1; i <= n; i++)	dis[i] = 99999933;
	dis[s] = 0;
	q.push((dot){s, 0});
	dijistra();
	for (int i = 1; i <= n; i++)
		cout << dis[i] << " ";
	return 0;
}