DFS_SPFA

最短路

SPFA算法的优化及应用.pdf467.2kB

深搜版的 $SPFA$
使用贪心预处理以及迭代加深，可以得出一个高效的深搜 $SPFA$
具体细节可以直接看上面的论文

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
typedef long long LL;
const int MAXN = 10000+9;
const int MAXM = 500000+9;
int n,m;
struct E{
    int next,to;
    LL val;
}edge[MAXM];
int head[MAXN],edge_num;
int S;
LL dis[MAXN];
void addedge(int x,int y,LL v){
    edge[++edge_num].next=head[x];
    edge[edge_num].to=y;
    edge[edge_num].val=v;
    head[x]=edge_num;
}
void Build(){
    scanf("%d%d%d",&n,&m,&S);
    for(int i=1;i<=m;i++){
        int a,b;
        LL c;
        scanf("%d%d%lld",&a,&b,&c);
        addedge(a,b,c);
    }
    for(int i=1;i<=n;i++)
        dis[i]=INT_MAX;
    dis[S]=0;
}
bool SPFA_INIT(int x,int step,int lim){
    if(step==lim)return true;
    for(int i=head[x];i;i=edge[i].next){
        if(dis[edge[i].to]>dis[x]+edge[i].val){
            dis[edge[i].to]=dis[x]+edge[i].val;
            SPFA_INIT(edge[i].to,step+1,lim);
            return true;
        }
    }
    return false;
}
void SPFA(int x,int step,int lim){
    if(step==lim)
        return;
    for(int i=head[x];i;i=edge[i].next){
        if(dis[edge[i].to]>dis[x]+edge[i].val){
            dis[edge[i].to]=dis[x]+edge[i].val;
            SPFA(edge[i].to,step+1,lim);
        }
    }
}
int main(){
    Build();
    for(int i=0;(1<<i-1)<=n;i++){
        int depth=1<<i;
        for(int j=1;j<=n;j++){
            if(SPFA_INIT(j,0,depth)){
                for(int k=1;k<=n;k++){
                    SPFA(k,0,depth);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    return 0;
}