#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诈尸了!