在此题中，spfa死了，但是我看到题解中有用随机化 spfa AC此题，我也尝试去用，并加了一个自己想的优化

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <ctime>
#define int long long
using namespace std;
const int MAXN=2e5+5;
template<typename T_>
struct stack{
	T_ S[MAXN];
	int tot=0;
	void push(T_ a){
		S[++tot]=a;
		//if(S[tot]>S[1]) swap(S[tot],S[1]);
		if(median()>S[tot]) swap(S[tot/2+1],S[tot]);
	}
	T_ top(){
		return S[tot];
	}
	void pop(){
		tot--;
	}
	void Ssort(){
		sort(S+1,S+1+tot,greater<int>());
	}
	bool empty(){
		return (tot==0?1:0);
	}
	int size(){
		return tot;
	}
	int median(){
		if(tot%2){
			return S[tot/2+1];
		}else{
			return (S[tot/2]+S[tot/2+1])/2;
		}
	}
}; 
struct node{
	int to,val;
	node(){}
	node(int T,int V){
		to=T,val=V;
	}
};
vector<node> G[MAXN];
void add(int a,int b,int c){
	G[a].push_back(node(b,c));
}
int n,m,s,vis[MAXN],tim[MAXN],dis[MAXN];
void SPFA(int S){
	stack<int> q;
	for(int i=1;i<=MAXN;i++){
		dis[i]=0x3f3f3f3f3f3f3f;
	}
	q.push(s);
	dis[S]=0;
	vis[S]=1;
	tim[S]++;
	while(!q.empty()){
		if(rand()%10000==0) q.Ssort();
		int now=q.top();
		q.pop();
		vis[now]=0;
		int len=G[now].size();
		for(int i=0;i<len;i++){
			int y=G[now][i].to,w=G[now][i].val;
			if(dis[y]>dis[now]+w){
				dis[y]=dis[now]+w;
				if(vis[y]==0){
					vis[y]=1;
					q.push(y);
					tim[y]++;
				}
			}
		}
	}
	bool flag=0;
	for(int i=1;i<=n;i++){
		printf("%lld ",dis[i]);
	}
}
signed main(){
	srand(time(0));
	scanf("%lld %lld %lld",&n,&m,&s);
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		add(a,b,c);
	}
	SPFA(s);
}

T 了第一个点，但是如果我把随机化排序的那一行删去，代码变成了

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <ctime>
#define int long long
using namespace std;
const int MAXN=2e5+5;
template<typename T_>
struct stack{
	T_ S[MAXN];
	int tot=0;
	void push(T_ a){
		S[++tot]=a;
		//if(S[tot]>S[1]) swap(S[tot],S[1]);
		if(median()>S[tot]) swap(S[tot/2+1],S[tot]);
	}
	T_ top(){
		return S[tot];
	}
	void pop(){
		tot--;
	}
	void Ssort(){
		sort(S+1,S+1+tot,greater<int>());
	}
	bool empty(){
		return (tot==0?1:0);
	}
	int size(){
		return tot;
	}
	int median(){
		if(tot%2){
			return S[tot/2+1];
		}else{
			return (S[tot/2]+S[tot/2+1])/2;
		}
	}
}; 
struct node{
	int to,val;
	node(){}
	node(int T,int V){
		to=T,val=V;
	}
};
vector<node> G[MAXN];
void add(int a,int b,int c){
	G[a].push_back(node(b,c));
}
int n,m,s,vis[MAXN],tim[MAXN],dis[MAXN];
void SPFA(int S){
	stack<int> q;
	for(int i=1;i<=MAXN;i++){
		dis[i]=0x3f3f3f3f3f3f3f;
	}
	q.push(s);
	dis[S]=0;
	vis[S]=1;
	tim[S]++;
	while(!q.empty()){
		int now=q.top();
		q.pop();
		vis[now]=0;
		int len=G[now].size();
		for(int i=0;i<len;i++){
			int y=G[now][i].to,w=G[now][i].val;
			if(dis[y]>dis[now]+w){
				dis[y]=dis[now]+w;
				if(vis[y]==0){
					vis[y]=1;
					q.push(y);
					tim[y]++;
				}
			}
		}
	}
	bool flag=0;
	for(int i=1;i<=n;i++){
		printf("%lld ",dis[i]);
	}
}
signed main(){
	srand(time(0));
	scanf("%lld %lld %lld",&n,&m,&s);
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		add(a,b,c);
	}
	SPFA(s);
}

在时间上却快了很多，但是还是过不了第一个数据点

请问我的优化也就是

if(median()>S[tot]) 
	swap(S[tot/2+1],S[tot]);

为什么有如此大的用处？