#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define F 15
#define R 200
#define INF 0x7fffffff
vector<pair<int,int> > g[MAXN];
int n,m,s,dis[MAXN],cnt[MAXN];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void SPFA(){
    deque<int> q;
    q.push_back(s);
    while(!q.empty()){
        int u=q.front();
        q.pop_front();
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i].first,w=g[u][i].second;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(cnt[v]>R){
                    q.push_back(v);
                }else if(dis[q.front()]>=dis[v]-F){
                    q.push_front(v);
                }else{
                    q.push_back(v);
                }
                cnt[v]++;
            }
        }
    }
}
int main(){
    srand(time(NULL));
    n=read();
    m=read();
    s=read();
    for(int i=1;i<=m;i++){
        int u,v,w;
        u=read();
        v=read();
        w=read();
        g[u].push_back(make_pair(v,w));
    }
    for(int i=1;i<=n;i++){
        random_shuffle(g[i].begin(),g[i].end());
    }
    fill(dis+1,dis+1+n,INF);
    dis[s]=0;
    SPFA();
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    printf("\n");
    return 0;
}

评测记录

我加上了带容错SLF，mcfx，还有边序随机，然后就AC了？

SPFA诈尸了！