Dijkstra如何堆优化？

题目描述 Description
现有一图，图上有N个点，M条边，边为有向边，每条边有一个权值，权值非负。
先给你一点a，请你求出从a出发到每个点的距离，如果一个点无法到达则输出-1。

输入描述 Input Description
第一行 三个整数n,m,a
接下来m行，每行三个非负整数Xi,Yi,Li，表示从Xi到Yi有一条权值为Li的有向边

输出描述 Output Description
一行，n个数，表示到每个点的距离。如果没有最短距离，输出-1

样例输入 Sample Input
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
样例输出 Sample Output
0 2 4 3
数据范围及提示 Data Size & Hint
1≤n≤100000
1≤m≤200000
a=1
0≤Wi≤10^9
0≤∑Wi≤10^9

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
struct edge {
  int to;
  long long w;	//to下一个点，w边权值 
};
vector<edge> g[100001];
int n, m, s;
long long dis[100001];	//dis[i]存到i点的最短路径 
bool found[100001];	//found[i]记录第i个点最短路径是否确定 
void Dijkstra(int st)	//原点为st，dijkstra算最短路径 
{
	memset(dis, 0x3f3f3f3f, sizeof(dis));	//先把所有点的最短路径初始化无穷大
	dis[st]=0;//原点的最短路径置为1
	while(true)//不断重复以下过程，直到所有点变为蓝点
	{
		int u=-1;
		int minn=0x3f3f3f3f;
		//每次找到左右白点中路径值最小的点
		for(int i=1; i<=n; i++)
			if(!found[i] && (u==-1||dis[i]<dis[u]))
				u=i;
		if(u==-1)
			break;
		found[u]=true;	//变为蓝点
		//从这个点出发，对它出边的点进行松弛操作 
		for(int i=0; i<g[u].size(); i++)
		{
			edge e=g[u][i];
			if(!found[e.to])
				dis[e.to]=min(dis[e.to], dis[u]+e.w);
		}
	}
	
}
int main()
{
	scanf("%d%d%d", &n, &m, &s);
	while(m--)
	{
		int u, v;
		long long w;
		scanf("%d%d%lld",&u,&v,&w);
		g[u].push_back((edge){v,w});
	}
	Dijkstra(s);
	for(int i=1; i<=n; i++)
		if(dis[i]==0x3f3f3f3f)
			cout << (-1) << ' ';
		else
			cout << dis[i] << ' ';
	return 0;
}