求更nb的spfa优化

经过不懈努力，在spfa的各种优化下，成功获得了84分，求更nb的优化

#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);
}

验证码:g8tg祭