提交记录

#include<bits/stdc++.h>
using namespace std;
int getrand(int l,int r){
    int total=r-l+1;
    int x=1ll*rand()*rand();
    int y=rand();
    return l+((x^y)%total+total)%total;
}
const int N=1e5+5;
vector<pair<int,int>>to_and_w[N];
int dis[N];
bool vis[N];
int stk[N];
int total;
bool cmp(int x,int y){
    return dis[x]>dis[y];
}
void SPFA(int n,int s){
    fill(dis,dis+N,(int)1e9);
    dis[s]=0;
    vis[s]=1;
    stk[total++]=s;
    while(total){
        if(!(getrand(1,(int)1e8)%(total))){
            sort(stk,stk+total,cmp);
        }
        int u=stk[--total];
        vis[u]=0;
        for(auto i:to_and_w[u]){
            int v=i.first,w=i.second;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    vis[v]=1;
                    stk[total++]=v;
                }
            }
        }
    }
}
int main(){
    srand(time(0));
    ios::sync_with_stdio(0);
    int n,m,s;
    cin>>n>>m>>s;
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        to_and_w[u].push_back({v,w});
    }
    SPFA(n,s);
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
    }
    return 0;
}