SLF 带容错求调

P4779 【模板】单源最短路径(标准版)

BYR_KKK @ 2024-11-29 11:26:44

wa#1,不知道为啥能错/yun

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define debug(...) fprintf(stderr,##__VA_ARGS__)

template<typename T>
void read(T &x){
    x=0;
    int f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') x=x*10+(int)(c-'0'),c=getchar();
    x*=f;
}

std::stack<char>st;
template<typename T>
void print(T x){
    if(x==0) putchar('0');
    if(x<0) putchar('-'),x=-x;
    while(st.size()) st.pop();
    while(x) st.push((char)('0'+x%10)),x/=10;
    while(st.size()) putchar(st.top()),st.pop();
}

template<typename T>
void printsp(T x){
    print(x),putchar(' ');
}

template<typename T>
void println(T x){
    print(x),putchar('\n');
}

template<typename T,typename I>
void chkmin(T &a,I b){
    a=std::min(a,b);
}

template<typename T,typename I>
void chkmax(T &a,I b){
    a=std::max(a,b);
}

bool Mbe;

const int inf=1e18,MOD1=998244353,MOD2=1e9+7;

const int maxn=1e5+10;

std::vector<std::pair<int,int> >a[maxn];

int n,m,s;

bool in[maxn];

int sum[maxn],dis[maxn],tot;

bool spfa(int s){
    int B=(int)(std::sqrt(tot));
    std::deque<int>q;
    for(int i=1;i<=n;i++) dis[i]=inf,in[i]=0;
    in[s]=1,dis[s]=0,q.push_front(s);
    while(q.size()){
        int x=q.front();
        q.pop_front();
        in[x]=0;
        if(++sum[x]>n+1) return 0;
        for(std::pair<int,int>p:a[x]){
            if(dis[p.fi]>dis[x]+p.se){
                dis[p.fi]=dis[x]+p.se;
                if(in[p.fi]) continue;
                in[p.fi]=1;
                if(!q.size()) q.push_back(p.fi);
                else if(dis[p.fi]>dis[q.front()]+B) q.push_back(p.fi);
                else q.push_front(p.fi);
            }
        }
    }
    return 1;
}

bool Men;

signed main(){
    debug("%.6lfMB\n",(&Mbe-&Men)/1048576.0);
    read(n),read(m),read(s);
    for(int i=1;i<=m;i++){
        int u,v,w;
        read(u),read(v),read(w);
        a[u].push_back({v,w});
        tot+=w;
    }
    // assert(tot<=1e9);
    spfa(s);
    for(int i=1;i<=n;i++) printsp(std::min(dis[i],215748364777ll));
    debug("%.6lfms\n",1e3*clock()/CLOCKS_PER_SEC);
}

by JuRuoOIer @ 2024-11-29 13:01:02

卷狗 nmsl


|