将弱化版（题解）的代码复制过来，你会发现 0 TLE。

如何优化呢？

思路

NO.1：优先队列优化

每次运算时都要找距离最短的点，所以我们用循环来找这个点，导致时间变成 $O(n^2)$ 。

所以我们可以把找的时间优化掉，用优先队列的自动排序直接帮我们拿到最小的值，将时间缩减到 $O(n \cdot logn)$。

但，那样会打乱顺序。所以我们需要存下标，用到 pair。你可能会问优先队列怎么自定义排序，但有个更好的方法。把值（距离）存到第一位，因为优先队列面对结构体、pair 是去排序第一个值的。

注意：优先队列是从大到小排序，但可以存相反数来排序

NO.2：防止多次松弛

由于优先队列没有去重功能，所以一个数可能多次被推进队列，就有很多次处理的点是处理过的。在处理点时看看有没有处理过这个点，有的话就 continue，就可以防止无效处理了。

注意：不要用 set，因为它每次推入新元素时都会去重排列，比优先队列耗费更多时间

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100005,M = 200005,INF = 1073741823;

// 链式前向星
struct edge{
	int v,w,prev;
}edges[M];
int tail[N],tot;
void add_edge(int u,int v,int w){
	edges[++tot] = {v,w,tail[u]};
	tail[u] = tot;
}

int dis[N],n,m,s;
bool f[N];
void dkstr(){
	priority_queue<pair<int,int>> q;	// 第一个值存起点到第 i 个点的距离的相反值，第二个值存点的编号
	q.push({0,s});
	while (!q.empty()){
		int u = q.top().second;
		q.pop();
		if (f[u])	continue;	// 由于可能被多次放进队列（松弛），所以当这个点已经算完了就不用再算了
		f[u] = 1;
		for (int j = tail[u];j;j = edges[j].prev){
			int v = edges[j].v,w = edges[j].w;
			if (!f[v] && dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				q.push({-dis[v],v}); // 存相反数以从小到大排序
			}
		}
	}
}
int main(int argc, char **argv){
	fill(dis,dis + N,INF);
	cin >> n >> m >> s;
	dis[s] = 0;
	for (int i = 0;i < m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		add_edge(u,v,w);
	}
	dkstr();
	for (int i = 1;i <= n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}