SPFA又被我救活了

· · 个人记录

书接上回

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define getchar_fread() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(buffer,1,q1+1,stdout),q1=-1)
const int MAXN=1<<15,N=1e6+8,M=5e6+8;
const ll C=0x3f3f3f3f3f3f3f3f;
char *p1,*p2,buf[MAXN],buffer[MAXN];
int q1=-1,q2=MAXN-1,j=0;
inline void putchar_fwrite(char x){if (q1==q2) flush();buffer[++q1]=x;}
template<typename T>
inline void read(T &x){x=0;
    T c=getchar_fread(),f=0;
    while(!isdigit(c)){if(c=='-') f=1;c=(T)getchar_fread();}
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=(T)getchar_fread();
    if (f) x=~x+1;
}
template<typename T>
inline void write(T x){
    if (x<0) putchar_fwrite('-'),x=~x+1;
    T print[65];
    while (x) print[++j]=x%10,x/=10;
    if (j==0) print[++j]=0;
    while (j) putchar_fwrite(print[j--]^48);
}
struct G{int x,t,qq;ll u;} a[M];
int n,m,h[N],cnt=0;
struct Tar{int dfn,low;} g[N];
ll ans[N],z;
int p[N],c[N],l,stk[N],top=0,w[N],k[N],t[N],u,v;
void tarjan(int x){
    g[x].dfn=g[x].low=++l;
    stk[++top]=x;k[x]=w[x]=1;
    for (int i=h[x];i;i=a[i].t){v=a[i].x;
        if (a[i].qq==0) continue;
        if (g[v].dfn&&k[v]) --p[v];
        if (!g[v].dfn) tarjan(v);
        if (w[v]) g[x].low=min(g[x].low,g[v].low);
    }if (g[x].dfn==g[x].low){
        int y=0;
        while (x!=y) y=stk[top--],w[y]=0;
    }k[x]=0;
}
struct pri{
    int x;ll u;
    inline bool operator<(const pri&other)const{return u>other.u;}
};
struct spf{
    int x,f,t,dep;
    inline bool operator<(const spf&other)const{
        if (t!=other.t) return t<other.t;
        return dep>other.dep;
    }
};
template <typename T>
class Priority_Queue:public priority_queue<T>{
    public:void reserve(size_t n){this->c.reserve(n);}
};
inline void init(int s){
    memset(g,0,sizeof(g));
    memset(p,0,sizeof(p));
    memset(w,0,sizeof(w));
    memset(t,0,sizeof(t));
    memset(c,0,sizeof(c));
    memset(ans,C,sizeof(ans));
    for (int i=1;i<=cnt;++i) a[i].qq=0;
    Priority_Queue <pri> q;
    q.reserve(m);ans[s]=0;
    w[s]=s;q.push({s,0});l=0;
    while (!q.empty()){
        u=q.top().x;q.pop();
        if (c[u]) continue;
        ++l;if (l==n) break;
        for (int i=h[u];i;i=a[i].t){v=a[i].x;
            if (v==w[u]) continue;
            ++p[v];a[i].qq=1;
            if (ans[v]>ans[u]+a[i].u){
                ans[v]=ans[u]+a[i].u,w[v]=u,c[v]=c[u]+1;
                if (c[v]==0) q.push({v,a[i].u});
            }
        }
    }
    memset(w,0,sizeof(w));
    l=0,tarjan(s);
    memset(w,0,sizeof(w));
    w[s]=t[s]=1;
}
inline bool spfa(int s){
    Priority_Queue <spf> sta;
    init(s);sta.reserve(n);
    sta.push({s,1,1,1});
    while (!sta.empty()){
        spf tp=sta.top();u=tp.x;
        sta.pop();w[u]=0;
        if (c[u]>n) return 0;
        for (int i=h[u];i;i=a[i].t){l=0,v=a[i].x;
            if (ans[v]>ans[u]+a[i].u)
                c[v]=c[u]+1,ans[v]=ans[u]+a[i].u,l=1;
            if (!w[v]&&(p[v]==1&&tp.f||l&&p[v]==0)) w[v]=1,sta.push({v,p[v],++t[v],c[v]});
            if (tp.f&&p[a[i].x]>0) --p[a[i].x];
        }
    }return 1;
}
signed main(){
    int s;
    read(n),read(m),read(s);
    for (int i=1,x,y,z;i<=m;++i){
        read(x),read(y),read(z);
        if (x==y) continue;
        a[++cnt]={y,h[x],0,z};h[x]=cnt;
    }
    if (!spfa(s)) return cout <<"No answer.",0;
    for (int i=1;i<=n;++i) write(ans[i]),putchar_fwrite(' ');
    flush();
    return 0;
}
//拓扑排序、最小生成树思想与加速路径传播优化spfa

初测时间复杂度为O((n+m)logn)，可以判负权图