专栏文章

SPFA 优化之旅

ppengyulun
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mlgxw2tt
此快照首次捕获于
2026/02/11 02:33
上周
此快照最后确认于
2026/02/11 02:33
上周
查看原文
第一版：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+8,M=2e6+8,C=0x3f3f3f3f;
struct G{int x,u,t;} a[M<<1];
int n,m,h[N],cnt=0;
struct Tar{int dfn,low;} p2[N];
int fa[N],ans[N],p[N];
int w[N],l,stk[N],top=0;
inline void spfa(int s){
    queue <int> sta;
    memset(ans,C,sizeof(ans));
    memset(w,0,sizeof(w));
    sta.push(s);
    w[s]=1;ans[s]=0;
    while (!sta.empty()){
        int u=sta.front(),k;
        sta.pop();w[u]=0;
        for (int i=h[u];i;i=a[i].t){k=0;
            if (ans[a[i].x]>ans[u]+a[i].u)
                ans[a[i].x]=ans[u]+a[i].u,k=1;
            if (w[a[i].x]==0&&(p[a[i].x]==1||k&&p[a[i].x]==0)) w[a[i].x]=1,sta.push(a[i].x);
            if (p[a[i].x]>0) --p[a[i].x];
        }
    }
}
void tarjan(int x){
    p2[x].dfn=p2[x].low=++l;
    stk[++top]=x;w[x]=1;
    for (int i=h[x];i;i=a[i].t){
        if (p2[a[i].x].dfn&&w[a[i].x]) --p[a[i].x];
        if (!p2[a[i].x].dfn) tarjan(a[i].x);
        if (w[a[i].x]) p2[x].low=min(p2[x].low,p2[a[i].x].low);
    }
    if (p2[x].dfn==p2[x].low){
        int y=0,sz=0;
        while (x!=y) y=stk[top--],sz++,w[y]=0;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);int s;
	cin >>n>>m>>s;
	for (int i=1,x,y,z;i<=m;i++){
	    cin >>x>>y>>z;
	    if (x==y) continue;
	    p[y]++;
	    cnt++;a[cnt]={y,z,h[x]};h[x]=cnt;
	}
	tarjan(s);spfa(s);
	for (int i=1;i<=n;i++) cout <<ans[i]<<" ";
	return 0;
}
第二版：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+8,M=5e5+8,C=0x3f3f3f3f;
struct G{int x,u,t;} a[M];
int n,m,h[N],cnt=0;
struct spf{
    int x,dep;
    inline bool operator<(const spf& other)const{return dep>other.dep;}
};
struct Tar{int dfn,low;} g[N];
int fa[N],ans[N],p[N],dep[N],l,stk[N],top=0;;
bool w[N];
inline void spfa(int s){
    memset(ans,C,sizeof(ans));
    memset(w,0,sizeof(w));
    priority_queue <spf> sta;
    sta.push({s,dep[s]});
    w[s]=1;ans[s]=0;
    while (!sta.empty()){
        int u=sta.top().x,k;
        sta.pop();w[u]=0;
        for (int i=h[u];i;i=a[i].t){k=0;
            if (ans[a[i].x]>ans[u]+a[i].u)
                ans[a[i].x]=ans[u]+a[i].u,k=1;
            if (w[a[i].x]==0&&(p[a[i].x]==1||k&&p[a[i].x]==0)) w[a[i].x]=1,sta.push({a[i].x,dep[a[i].x]});
            if (p[a[i].x]>0) --p[a[i].x];
        }
    }
}
void tarjan(int x){
    g[x].dfn=g[x].low=++l;
    stk[++top]=x;w[x]=1;
    for (int i=h[x];i;i=a[i].t){
        if (g[a[i].x].dfn&&w[a[i].x]) --p[a[i].x];
        if (!g[a[i].x].dfn) tarjan(a[i].x);
        if (w[a[i].x]) g[x].low=min(g[x].low,g[a[i].x].low);
    }
    if (g[x].dfn==g[x].low){
        int y=0;
        while (x!=y) y=stk[top--],w[y]=0;
    }
}
inline void bfs(int s){
    queue <int> sta;
	memset(w,0,sizeof(w));
	sta.push(s);
	w[s]=1;dep[s]=1;
	while (!sta.empty()){
		int u=sta.front();
		sta.pop();
		for (int i=h[u];i;i=a[i].t){
			++p[a[i].x];
			if (w[a[i].x]==0) dep[a[i].x]=dep[u]+1,w[a[i].x]=1,sta.push(a[i].x);
		}
	}
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int s;
	cin >>n>>m>>s;
	for (int i=1,x,y,z;i<=m;++i){
	    cin >>x>>y>>z;
	    if (x==y) continue;
	    a[++cnt]={y,z,h[x]};h[x]=cnt;
	}
	bfs(s);
	memset(w,0,sizeof(w));
	tarjan(s);
	spfa(s);
	for (int i=1;i<=n;i++) cout <<ans[i]<<" ";
	return 0;
}
第三版：
CPP
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1<<18,N=1e6+8,M=3e6+8;
char *p1,*p2,buf[MAXN],buffer[MAXN];
int q1=-1,q2=MAXN-1,j=0;
ll ans[N],C=0x3f3f3f3f3f3f3f3f;
struct G{int x,u,t;} a[M];
struct Tar{int dfn,low;} g[N];
int n,m,h[N],cnt=0;
struct spf{
    int x,dep;
    inline bool operator<(const spf& other)const{return dep>other.dep;}
};
int p[N],dep[N],c[N],l,stk[N],top=0;
bool w[N];
#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)
template<typename T>
inline void read(T &x){
    x=0;
    T c=getchar_fread();
    while(!isdigit(c)) c=(T)getchar_fread();
    while(isdigit(c)) x=(x<<3)+(x<<1)+c-48,c=(T)getchar_fread();
}
inline void putchar_fwrite(char x){if (q1==q2) flush();buffer[++q1]=x;}
template<typename T>
inline void write(T x){
	T print[65];
	while (x) print[++j]=x%10,x/=10;
	if (j==0) print[++j]=0;
	while (j) putchar_fwrite(print[j--]+48);
}
inline bool spfa(int s){
    memset(ans,C,sizeof(ans));
    memset(w,0,sizeof(w));
    priority_queue <spf> sta;
    sta.push({s,dep[s]});
    w[s]=1;ans[s]=0;c[s]=1;
    while (!sta.empty()){
        int u=sta.top().x,k;
        sta.pop();w[u]=0;
		if (c[u]>n) return 0;
        for (int i=h[u];i;i=a[i].t){k=0;
            if (ans[a[i].x]>ans[u]+a[i].u)
                c[a[i].x]=c[u]+1,ans[a[i].x]=ans[u]+a[i].u,k=1;
            if (w[a[i].x]==0&&(p[a[i].x]==1||k&&p[a[i].x]==0)) w[a[i].x]=1,sta.push({a[i].x,dep[a[i].x]});
            if (p[a[i].x]>0) --p[a[i].x];
        }
    }
    return 1;
}
void tarjan(int x){
    g[x].dfn=g[x].low=++l;
    stk[++top]=x;w[x]=1;
    for (int i=h[x];i;i=a[i].t){
        if (g[a[i].x].dfn&&w[a[i].x]) --p[a[i].x];
        if (!g[a[i].x].dfn) tarjan(a[i].x);
        if (w[a[i].x]) g[x].low=min(g[x].low,g[a[i].x].low);
    }if (g[x].dfn==g[x].low){
        int y=0;
        while (x!=y) y=stk[top--],w[y]=0;
    }
}
inline void bfs(int s){
    queue <int> sta;
	memset(w,0,sizeof(w));
	sta.push(s);
	w[s]=1;dep[s]=1;
	while (!sta.empty()){
		int u=sta.front();
		sta.pop();
		for (int i=h[u];i;i=a[i].t){
			++p[a[i].x];
			if (w[a[i].x]==0) dep[a[i].x]=dep[u]+1,w[a[i].x]=1,sta.push(a[i].x);
		}
	}
}
signed main(){
    int s;ll z;
	read(n),read(m),read(s);
	for (int i=1,x,y,z;i<=m;++i){
	    read(x),read(y),read(z);
	    a[++cnt]={y,z,h[x]};h[x]=cnt;
	}
	bfs(s);
	memset(w,0,sizeof(w));
	tarjan(s);
	if (spfa(s)==0){
		cout <<"No answer.";
		return 0;
	}
	for (int i=1;i<=n;i++) write(ans[i]),putchar_fwrite(' ');
	flush();
	return 0;
}
第四版：
CPP
#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
第五版：
CPP
//拓扑排序、最小生成树思想与加速路径传播优化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)
#define add(x,y,z) (a[++cnt]={y,h[x],0,z},h[x]=cnt)
const int MAXN=1<<16,N=8e5+8,M=2e6+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,ks,dsu[N];
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,fau[N];
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);}
};
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
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(fau,0,sizeof(fau));
    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;
    q.push({s,0});l=0;c[s]=1;
	while (!q.empty()){
		u=q.top().x;q.pop();
		if (w[u]) continue;
		++l;w[u]=1;if (l==n) break;
		for (int i=h[u];i;i=a[i].t){v=a[i].x;
		    if (v==fau[u]) continue;
			++p[v];a[i].qq=1;
			if (ans[v]>ans[u]+a[i].u){
    			ans[v]=ans[u]+a[i].u,fau[v]=u,c[v]=c[u]+1;
    			if (w[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;ks=0;
}
inline bool check(){
	if (ks<m) return 0;
	ks=0;
	for (int i=1;i<=n;++i) dsu[i]=i;
	for (int i=1,dx,dy;i<=n;++i){
		dx=find(fau[i]),dy=find(i);
		if (dx==dy) return 1;
		dsu[dy]=dx;
	}
	return 0;
}
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||check()) return 0;
        for (int i=h[u];i;i=a[i].t){
			l=0,v=a[i].x;++ks;
            if (ans[v]>ans[u]+a[i].u)
                c[v]=c[u]+1,ans[v]=ans[u]+a[i].u,fau[v]=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;i<=m;++i){
	    read(x),read(y),read(z);
	    if (x==y) continue;
	    add(x,y,z);
	}
	if (!spfa(s)) return cout <<"No answer.",0;
	for (int i=1;i<=n;++i) write(ans[i]),putchar_fwrite(' ');
	flush();
	return 0;
}
就此，spfa优化完成。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...